perm filename KRD5.TEX[AM,DBL]1 blob
sn#543031 filedate 1980-11-19 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00034 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00005 00002 \init{
C00006 00003 \chapbegin{5} % Here beginneth Chapter 5
C00008 00004 \lsectionbegin[2]2{Trace of System Performance:}{Debugging example continued}
C00047 00005 \sectionbegin[3]{Rule model overview}
C00050 00006 \subsectionbegin[3.1]{Perspective: Model-Based Computer Vision}
C00058 00007 \subsectionbegin[3.2]{Rule Models: Overview}
C00070 00008 \subsectionbegin[3.3]{Rule Models: Example}
C00076 00009 \subsectionbegin[3.3.1]{Details of the DESCRIPTION Implementation}
C00082 00010 \subsectionbegin[3.4]{Rule Models as Concept Formation}
C00088 00011 \subsectionbegin[3.5]{Implications}
C00096 00012 \sectionbegin[3.6]{Character and Use of the Models}
C00100 00013 \sectionbegin[4]{How it all works}
C00103 00014 \subsectionbegin[4.1]{Tracking Down the Bug}
C00120 00015 \subsectionbegin[4.2]{Deciphering the English Text}
C00128 00016 \subsectionbegin[4.2.1]{Terminology and Dictionary Structure}
C00132 00017 \subsectionbegin[4.2.2]{Pre-processing the Text}
C00136 00018 \subsectionbegin[4.2.3]{Checking the Rule Model}
C00142 00019 \subsectionbegin[4.2.4]{Generating a LISP Clause}
C00159 00020 \subsectionbegin[4.2.5]{Scoring the Parses}
C00161 00021 \subsectionbegin[4.3]{Checking Results}
C00171 00022 \subsectionbegin[4.4]{Second Guessing}
C00180 00023 \subsectionbegin[4.5]{Final Checkout}
C00184 00024 \subsectionbegin[4.6]{Bookkeeping}
C00190 00025 \subsectionbegin[4.7]{Rerunning the Consultation}
C00191 00026 \sectionbegin[5]{Other Uses for the Rule Models}
C00201 00027 \sectionbegin[6]{Personalized world views}
C00204 00028 \sectionbegin[7]{More on models and concept formation}
C00215 00029 \subsectionbegin[7.2]{Concept Formation}
C00217 00030 \subsectionbegin[7.3]{A Synthesis}
C00222 00031 \sectionbegin[8]{Assumptions and Limitations}
C00227 00032 \sectionbegin[9]{Unsolved problems and future work}
C00233 00033 \subsectionbegin[9.2]{Major Problems}
C00251 00034 \sectionbegin[10]{Summary}
C00253 ENDMK
C⊗;
\init{
\input cmpdes
\input temacs
\def\draft{T}
\titlepage
\newpage
\setcount0 63
\parttitle{TEIRESIAS: APPLICATIONS OF META-LEVEL KNOWLEDGE}
}
\baselineskip 12pt
\chapbegin{5} % Here beginneth Chapter 5
\chaptertitle{KNOWLEDGE ACQUISITION I}
\rjustline{\:B Knowledge Acquisition I}
\tenpoint
\vskip 13.7pc
\epigraph{Knowledge is that small part of ignorance that we arrange and classify.}
\author{Ambrose Bierce}
\epigraphend
\sectionbegin[1]{Introduction}
When last we left him in chapter 3, the expert had noticed
something wrong with the identities deduced and had tracked down the problem
himself, using the explanation facilities in {\TEIRESIAS}. In this chapter, the same
example is explored to show how the system can direct the debugging
process. Then, in order to present the entire interaction at once, the
example continues through the acquisition of a new rule that fixes the
problem. The remainder of the chapter presents a global overview of the
ideas used that make possible the system's performance and reviews the trace
in detail to explain the basis for some of the capabilities displayed.
\sectionskip
\lsectionbegin[2]2{Trace of System Performance:}{Debugging example continued}
It should be emphasized that this example has been chosen
because it displays, in a single pass, a large number of the features of
the system. In particular, it shows initial failure of the primary natural
language handling routines and allows the demonstration of many of the secondary
features. The interaction shown below is thus longer than most. As before,
annotations are in italics, and user responses in boldface capitals.
\null
{\tracebegin
My\ therapy\ recommendation\ will\ be\ based\ on\ the\ following\eol
probable\ infection(s)\ and\ potential\ causative\ organism(s):\eol
\eol
INFECTION-1\ is\ PRIMARY-BACTEREMIA\eol
\ \ \ \ <Item\ 1>\ \ E.COLI\ [ORGANISM-1]\eol
\ \ \ \ <Item\ 2>\ \ PSEUDOMONAS-AERUGINOSA\ [ORGANISM-1]\eol
\eol
Are\ all\ these\ identities\ correct?\eol
++**{\bf\ \ N}\eol
\traceend}
\scomm
{As before, the expert disagrees with the results and indicates to {\TEIRESIAS}
the identities that he thinks should have resulted.}
\ecomm
{\tracebegin
\eol
Are\ there\ any\ identities\ missing?\eol
++**{\bf\ \ Y}\eol
Which\ one(s)?\eol
++**{\bf\ \ KLEBSIELLA-PNEUMONIAE\ \ \ PROTEUS-NON-MIRABILIS}\eol
Are\ there\ any\ identities\ that\ shouldn't\ have\ appeared?\eol
++**{\bf\ \ Y}\eol
Which\ one(s)?\eol
++**{\bf\ \ PSEUDOMONAS-AERUGINOSA}\eol
\eol
Do\ you\ want\ to\eol
\ \ \ \ \ \ 1]\ track\ down\ the\ problem\ yourself,\ or\eol
\ \ \ \ \ \ 2]\ allow\ me\ to\ guide\ the\ debugging,\ or\eol
\ \ \ \ \ \ 3]\ ignore\ it\ for\ now\ and\ fix\ it\ another\ time?\eol
Type\ 1,\ 2\ or\ 3\eol
++**{\bf\ 2}\eol
\traceend}
\scomm
{Recall that in chapter 3 the expert followed option $\#$1.}
\ecomm
{\tracebegin
\eol
We'll\ start\ with\ the\ PSEUDOMONAS-AERUGINOSA\ first.\eol
\traceend}
\scomm
{This time, {\TEIRESIAS} will guide the process. Again it applies the heuristic
of starting with an identity that appeared incorrectly.}
\ecomm
{\tracebegin
\eol
The\ following\ rules\ were\ used\ in\ deducing\ that\ the\ identity\ of\eol
ORGANISM-1\ is\ pseudomonas-aeruginosa\eol
\eol
\eol
RULE184\eol
-------\eol
Since\ [1.1]\ the\ category\ of\ ORGANISM-1\ is\ not\ known\eol
\ \ \ \ \ \ [1.2]\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg\eol
\ \ \ \ \ \ [1.3]\ the\ morphology\ of\ ORGANISM-1\ is\ rod\eol
\ \ \ \ \ \ [1.4]\ the\ aerobicity\ of\ ORGANISM-1\ is\ facultative\eol
\ There\ is\ weakly\ suggestive\ evidence\ (.3)\ that\ the\ identity\ of\eol
\ ORGANISM-1\ is\ pseudomonas-aeruginosa\eol
\eol
\eol
Is\ this\ rule\ correct?\eol
++**{\bf\ \ Y}\eol
Should\ its\ premise\ have\ failed\ for\ this\ case?\eol
++**{\bf\ \ Y}\eol
Which\ clause\ of\ the\ premise\ should\ have\ been\ false?\ [give\ $\#$]\eol
++**{\bf\ \ 1}\eol
\eol
\eol
No\ conclusions\ were\ reached\ concerning\ the\ category\ of\eol
ORGANISM-1.\eol
\eol
Should\ it\ have\ been\ possible\ to\ conclude\ a\ category?\eol
++**{\bf\ \ Y}\eol
\eol
Which\ one?\eol
++**{\bf\ \ ENTEROBACTERIACEAE}\eol
\eol
There\ were\ no\ rules\ successfully\ invoked\ in\ the\ attempt\ to\eol
deduce\ that\ the\ category\ of\ ORGANISM-1\ is\ enterobacteriaceae.\eol
\eol
The\ following\ (potentially\ applicable)\ rules\ were\ NOT\ executed\eol
because\ the\ starred\ [**]\ clause\ failed:\eol
\eol
\eol
RULE116\eol
-------\eol
If\ \ \ \ 1)\ the\ identity\ of\ ORGANISM-1\ is\ not\ known\eol
\ \ \ **\ 2)\ the\ gram\ stain\ of\ ORGANISM-1\ is\ not\ known\ **\eol
\ \ \ \ \ \ 3)\ the\ morphology\ of\ ORGANISM-1\ is\ not\ known\eol
\ \ \ \ \ \ 4)\ the\ site\ of\ CULTURE-1\ is\ csf\eol
\ \ \ \ \ \ 5)\ the\ infection\ is\ meningitis\eol
\ \ \ \ \ \ 6)\ the\ age\ (in\ years)\ of\ Albert\ Hall\ is\ less\ than\ or\eol
\ \ \ \ \ \ \ \ \ equal\ to\ .17\eol
then\ \ There\ is\ weakly\ suggestive\ evidence\ (.33)\ that\ the\eol
\ \ \ \ \ \ category\ of\ ORGANISM-1\ is\ enterobacteriaceae\eol
\eol
\eol
RULE050\eol
-------\eol
If\ \ \ \ 1)\ the\ morphology\ of\ ORGANISM-1\ is\ rod\eol
\ \ \ \ \ \ 2)\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg\eol
\ \ \ \ \ \ 3)\ the\ aerobicity\ of\ ORGANISM-1\ is\ facultative\eol
\ \ \ **\ 4)\ the\ infection\ with\ ORGANISM-1\ was\ acquired\ while\ the\eol
\ \ \ \ \ \ \ \ \ patient\ was\ hospitalized\ **\eol
then\ \ There\ is\ suggestive\ evidence\ (.7)\ that\ the\ category\ of\eol
\ \ \ \ \ \ ORGANISM-1\ is\ enterobacteriaceae\eol
\eol
\eol
Are\ all\ these\ rules\ correct?\eol
++**{\bf Y}\eol
Should\ any\ of\ them\ have\ been\ successfully\ invoked?\eol
++**{\bf\ N}\eol
\traceend}
\scomm
{This would be the case if one of the starred premise clauses was false because
it had been ``stepped on'' by yet another rule further back in the chain.}
\ecomm
{\tracebegin
\eol
Is\ there\ a\ rule\ missing?\eol
++**{\bf Y}\eol
\eol
Ok,\ then\ I\ need\ a\ rule\ that\ would\ allow\ me\ to\ deduce\ that\ the\eol
category\ of\ ORGANISM-1 is enterobacteriaceae.\eol
\eol
Would you like to give me such a rule now?\eol
++**{\bf Y}\eol
Good\ellipsis\eol
\eol
\traceend}
\scomm
{To review briefly: The expert is tracking down the reason why {\sc MYCIN}
incorrectly concluded that the identity was pseudomonas-aeruginosa. Shown below
is the sequence of rules which were involved:}\par
\null
{\tracebegin \eightpoint
IDENTITY\eol
GRAM STAIN **\eol
MORPHOLOGY\eol
SITE\eol
INFECTION\eol
AGE\ \ \ \ \ \ \ \ \ --- RULE116 -> \char'134\eol
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ >->\ CATEGORY\eol
MORPHOLOGY\ \ ---\ RULE050\ ->\ /\ \ \ \ GRAM\ STAIN\ \ ---\ RULE184\ --->\ IDENTITY = PSEUDOMONAS-\eol
GRAM\ STAIN\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ AEROBICITY\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ AERUGINOSA\eol
AEROBICITY\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ MORPHOLOGY\eol
HOSPITALIZED **\eol
\traceend}\sl
\null\commpara\noindent
Pseudomonas-aeruginosa appeared because RULE184 executed successfully.
This occurred in part because category was unknown.
Category was unknown because all rules to conclude it (50 and 116) failed.
Since the expert believes all existing rules are correct, the
knowledge base
must be missing a rule that will conclude about category; in particular, that
the category is enterobacteriaceae. This will cause category to be known,
inhibiting rule 184, fixing at least this first problem, the incorrect
conclusion about pseudomonas-aeruginosa.
\commpara
Note how sharply focused the issue has become, for both the expert and
{\TEIRESIAS}, as a result of the large amount of contextual information available.
The doctor is not being asked to ``discuss bacteremia''; instead, the
system can at\index{(|focus, in knowledge acquisition|)} this point say\par
\null\hangindent 40pt after 0\noindent{\tt
I need a rule that would allow me to deduce that the ca\-tegory of
ORGANISM-1 is enterobacteriaceae.}\par\null
\commpara\noindent
and it must be a rule which is invocable in the context of this patient. This
focus makes it easier for the expert to specify a rule that may never have been
explicitly stated or recognized as such. This can be an important advantage in
any domain where the knowledge is not yet fully formalized.
\commpara
The contextual information is useful for {\TEIRESIAS} as well. It
provides a number of expectations about the content of the rule that are
useful
both in understanding what the expert types in and in checking the new rule to
make sure that it does indeed solve the problem at hand. Details of this
process are explained below.
\commpara
The trace continues with the expert typing in the rule\ellipsis
\ecomm
{\tracebegin
\eol
The new rule will be called RULE383\eol
\ If:\ \ \ \ 1\ -\ \ {\bf\ THE\ PATIENT'S\ INFECTION\ IS\ PRIMARY-}\eol
\ \ \ \ \ \ \ \ \ \ \ \ \ {\bf\ BACTEREMIA}\eol
\ \ \ and\ \ 2\ -\ \ {\bf\ THE\ SITE\ IS\ ONE\ OF\ THE\ STERILE\ SITES}\eol
\ \ \ and\ \ 3\ -\ \ \eol
\ Then:\ \ 1\ -\ \ {\bf\ THERE\ IS\ EVIDENCE\ (.8)\ THAT\ THE\ CATEGORY\ IS}\eol
\ \ \ \ \ \ \ \ \ \ \ \ \ {\bf\ ENTEROBACTERIACEAE}\eol
\ \ \ and\ \ 2\ - \eol
\eol
This may take a few moments\ellipsis\eol
\traceend}
\scomm
{Generally, it takes on the order of 10 to 30 seconds of cpu time.}
\ecomm
{\tracebegin
\eol
\eol
This is my understanding of your rule:\eol
RULE383\eol
-------\eol
\ \ If:\ \ 1)\ Primary-bacteremia\ is\ an\ associated\ infection\ for\ \eol
\ \ \ \ \ \ \ \ \ \ which\ therapy\ should\ cover,\ and\eol
\ \ \ \ \ \ \ 2)\ The\ infection\ with\ the\ organism\ was\ acquired\ while\eol
\ \ \ \ \ \ \ \ \ \ the\ patient\ was\ hospitalized,\ and\eol
\ \ \ \ \ \ \ 3)\ The\ culture\ was\ taken\ from\ a\ sterile\ source,\ and\eol
\ \ \ \ \ \ \ 4)\ The\ organism\ is\ not\ normally\ found\ at\ this\ site\eol
\ \ Then:\ \ There\ is\ strongly\ suggestive\ evidence\ (.8)\ that\ the\eol
\ \ \ \ \ \ \ \ \ category of the organism is enterobacteriaceae\eol
\eol
\traceend}
\scomm
{{\TEIRESIAS}'s initial interpretation of the natural language is incorrect (recall
that the example was chosen in part for this reason). In the system's
first attempt to understand the rule, each line of the original text has
been interpreted as two clauses. This results primarily from the
word-by-word approach to meaning. For instance, despite the obvious
grammatical simplicity of the first line of text, the system used the word
``primary-bacteremia'' as the basis for generating the first clause, and it
used the word ``infection'' to generate the second. In the second line of
text the word ``sterile'' was responsible for clause $\#$3, and the word
``sites'' used as the basis for clause $\#$4. The details of this process are
explained below, where it will become clear that while the translation is
wrong, it is not unreasonable given the simple natural language facilities.
\commpara
Nor is it unreasonable that {\TEIRESIAS} has turned each line of English into
more than one premise clause. The expert is not restricted to typing the
English equivalent of a single premise clause on each line. If he were,
rather than typing ``{\tt the organism is a gram negative aerobic rod},'' he
would have to type three lines, ``{\tt the organism is gram negative},'' ``{\tt it
is aerobic},'' ``{\tt it is a rod}.'' The cost of this capability, however, is
shown here: It may result in spurious clauses.
\commpara
We will see later that while {\TEIRESIAS}'s interpretations are incorrect,
they are all ``reasonable'' and ``consistent,'' in light of the system's
somewhat primitive approach to natural language. The rest of the example
shows that even when the initial guesses are incorrect, straightening things out
may conceivably be very easy.}
\ecomm
{\tracebegin
\eol
Okay? (Yes or No)\eol
++**{\bf N}\eol
\traceend}
\scomm
{The expert indicates that there is a problem with the interpretation and
uses the system's rule editor to specify the changes needed.}
\ecomm
{\tracebegin
\eol
Change premise? \eol
++**{\bf Y}\eol
\eol
What clause should be changed in premise? \eol
(type HELP for list of commands)\eol
++**{\bf CHANGE 1}\eol
\eol
Suppose (1) were changed to read- \eol
\ \ \ \ \ \ \ \ 1\ -\ The infection is primary-bacteremia\eol
Would that be ok?\eol
++**{\bf Y}\eol
\traceend}
\scomm
{Several simple heuristics are invoked to select the next most likely
interpretation, based on the English source of this clause and the set of
interpretations already rejected. In this case, the second choice is correct.}
\ecomm
{\tracebegin
\eol
Then\ you'll\ probably\ want\ to\ delete:\eol
\ \ \ \ \ \ \ \ 2)\ The\ infection\ with\ the\ organism was acquired while \eol
\ \ \ \ \ \ \ \ \ \ \ the patient was hospitalized\eol
Correct?\eol
++** {\bf Y}\eol
\traceend}
\scomm
\index{consistency}
{{\TEIRESIAS} enforces consistency constraints on its interpretation of
the English text. One of these constraints indicates that if the new
interpretation of clause $\#$1 is correct, then clause $\#$2 must have arisen
spuriously. That is, the system realizes it cannot get {\rm both} the new
version of clause $\#$1 and the old clause $\#$2 from the same line of text, and
indicates this to the expert.}
\ecomm
{\tracebegin
\eol
Anything else?\eol
++**{\bf D 3}\eol
clause(s) 3 deleted.\eol
\traceend}
\scomm
{Realizing that there was another spurious clause, the expert deletes clause $\#$3,
but then has second thoughts about the one he chose, so he checks, using the
``?'' command.}
\ecomm
{\tracebegin
\eol
Anything else?\eol
++**{\bf ?}\eol
\ \ \ \ \ 1\ -\ the\ infection\ is\ primary-bacteremia\eol
\ and\ 2\ -\ \ \ <deleted>\eol
\ and\ 3\ -\ \ \ <deleted>\eol
\ and\ 4\ -\ the\ organism\ is\ not\ normally\ found\ at\ this\ site\eol
\traceend}
\scomm
{He then discovers that he has typed the wrong number, undoes the damage, and
deletes the one initially intended.}
\ecomm
{\tracebegin
\eol
Anything else?\eol
++**{\bf U 3}\eol
clause(s) 3 undeleted.\eol
\eol
Anything else?\eol
++**{\bf D 4}\eol
clause(s) 4 deleted.\eol
\traceend}
\scomm
{There is one last correction to be made (all commands can be abbreviated
to a single letter)\ellipsis }
\ecomm
{\tracebegin
\eol
Anything else?\eol
++**{\bf C 3}\eol
Suppose (3) were changed to read- \eol
\ \ \ \ \ \ \ \ 3\ -\ The\ site\ of\ the\ culture\ is\ one\ of:\ those\ sites\ that\ \eol
\ \ \ \ \ \ \ \ \ \ \ \ are normally sterile\eol
Would that be ok?\eol
++**{\bf Y}\eol
\eol
Anything else?\eol
++**{\bf ?}\eol
\ \ \ \ \ 1\ -\ the\ infection\ is\ primary-bacteremia\eol
\ and\ 2\ -\ \ \ <deleted>\eol
\ and\ 3\ -\ the\ site\ of\ the\ culture\ is\ one\ of:\ those\ sites\ that\eol
\ \ \ \ \ \ \ \ \ are\ normally\ sterile\eol
\ and\ 4\ -\ \ \ \<deleted>\eol
\eol
++**{\bf OK}\eol
\traceend}
\scomm
{\ellipsis and at last he's happy with the rule.}
\ecomm
{\tracebegin
\eol
Change action? \eol
++**{\bf N}\eol
\eol
This is my understanding of your rule:\eol
RULE383\eol
-------\eol
\ \ If:\ \ 1)\ The\ infection\ is\ primary-bacteremia,\ and\eol
\ \ \ \ \ \ \ 2)\ The\ site\ of\ the\ culture\ is\ one\ of:\ those\ sites\ that\eol
\ \ \ \ \ \ \ \ \ \ are\ normally\ sterile\eol
\ \ Then:\ \ There\ is\ strongly\ suggestive\ evidence\ (.8)\ that\ the\eol
\ \ \ \ \ \ \ \ category of the organism is enterobacteriaceae\eol
\eol
\eol
Okay? (Yes or No)\eol
++**{\bf Y}\eol
\traceend}
\scomm
{This is the classic test of comprehension: The original English text has been
turned into a rule coded in {\sc LISP}; the {\sc LISP} is then translated back
into English for approval. Compare the results with the expert's original
input. Now that the expert is satisfied that the system understands the rule as
he has entered it, {\TEIRESIAS} checks several things about the rule to see if
∪it is satisfied.}
\ecomm
{\tracebegin
\eol
I hate to criticize, Dr. Davis, but did you know that most \eol
rules about what the category of a organism might be, that \eol
mention- \eol
\ \ \ \ \ \ \ \ \ \ \ \ the\ site\ of\ a\ culture\eol
\ \ \ \ \ \ \ \ \ \ \ \ the\ infection\eol
ALSO\ mention-\ \eol
\ \ \ \ \ [A]\ -\ the portal of entry of a organism\eol
Shall I try to write a clause to account for [A] ? \eol
++**{\bf Y}\eol
\traceend}
\scomm
\index{ second guessing}{The mechanism that makes
possible this sort of ``second guessing'' by {\TEIRESIAS}
is explained in detail below. Briefly, the system maintains a model of\index{ model of knowledge}
the knowledge base. In checking to see how this new piece of information ``fits
in'' to that model, it discovers that its expectations have been only partially\index{ expectations}
met. It indicates to the expert what expectations were left unfulfilled and
asks if it should attempt to fill in the missing parts.}
\ecomm
{\tracebegin
\eol
How about- \eol
\ \ \ \ \ [A]\ The portal of entry of the organism is gi\eol
Ok? \eol
++**{\bf Y}\eol
\traceend}
\scomm
{The expert agreed to the inclusion of a clause about the portal of entry,
this determines which attribute to use. {\TEIRESIAS} examines its model of the
knowledge base to see which predicate function is likely to be the right
one; the model evidently suggested the function {\tt SAME}. Finally, in order
to fix the original bug, it must be possible to invoke the new rule for
this patient. Since, in answer to question 18 of the original consultation
(see Figure 3--10), the expert responded that the portal of entry
was {\bf GI}, this is a plausible guess at the value to use. This\index{ knowledge acquisition in context}
demonstrates another benefit of the ``knowledge acquisition in context''
methodology described in chapter 4.}
\ecomm
{\tracebegin
\eol
Also, most rules about what the category of a organism may be\eol
ALSO conclude about- \eol
\ \ \ \ \ [A]\ -\ the identity of a organism\eol
Shall I try to write a clause to account for [A] ? \eol
++**{\bf N}\eol
\traceend}
\scomm
{The system noticed another unfulfilled expectation concerning the action part
of the rule, but the expert always has the option of overriding the system's
suggestions, and does so.}
\ecomm
{\tracebegin
\eol
The rule now reads: \eol
RULE383\eol
-------\eol
\ \ If:\ \ 1)\ The\ infection\ is\ primary-bacteremia,\ and\eol
\ \ \ \ \ \ \ 2)\ The\ site\ of\ the\ culture\ is\ one\ of:\ those\ sites\ that\eol
\ \ \ \ \ \ \ \ \ \ are\ normally\ sterile,\ and\eol
\ \ \ \ \ \ \ 3)\ The\ portal\ of\ entry\ of\ the\ organism\ is\ gi\eol
\ \ Then:\ \ There\ is\ strongly\ suggestive\ evidence\ (.8)\ that\ the\eol
\ \ \ \ \ \ \ \ \ category of the organism is enterobacteriaceae\eol
\eol
\traceend}
\scomm
{Now that both the expert and {\TEIRESIAS} are satisfied with the rule,
there is a bit
of bookkeeping to do. First, the new rule is checked by the system (behind the
scenes) to be sure that there is nothing obviously wrong with it---for instance,
one of the tests insures that none of the premise clauses is currently known to
be false. This might have happened if the expert had mistakenly typed {\tt the
site is not one of the sterile sites}. Had this been the case, the system
would have noticed at this point that that clause was guaranteed to fail for the
current patient, and the expert would have been given the option of returning to
the rule editor to fix the problem. There are several other things the system
checks at this point, but this rule passes all the tests, and hence there is no
indication of any problem.}
\ecomm
{\tracebegin
\eol
Please describe briefly why you added (or changed) this rule.\eol
Type an empty line when done.\eol
++**{\bf THE SYSTEM FAILED TO REALIZE IT COULD CONCLUDE}\eol
++**{\bf CATEGORY, AND THIS ALLOWED RULE184 TO INCORRECTLY}\eol
++**{\bf CONCLUDE IDENTITY}\eol
++**\eol
\traceend}
\scomm
\index{ knowledge base management}{Over the years of
{\sc MYCIN} development, the experts associated with
the project have occasionally looked in astonishment at a rule which,
though it had been around for some time, seemed, superficially at least, to
make very little sense. The question then arises as to why that rule was
added to the knowledge base. To avoid this problem, the expert is required
to explain why he wrote (or changed) the rule.
\commpara
There are also a number of other bookkeeping-type chores that are
being attended to here (again, behind the scenes). {\TEIRESIAS} takes care of tagging
the rule with information that will simplify keeping track of
the large, and constantly changing, body of rules. We will see in a moment
how that information is accessed.}
\ecomm
{\tracebegin
\eol
RULE383 has now been added to the knowledge base.\eol
\eol
\ I will now re-run the consultation to check the effectiveness\eol
of your new rule. Get comfortable, since this may take a bit.\eol
\ \ \ \ \ Also, new questions may be asked as a result of this new \eol
rule. If a question is printed, please answer it with refe-\eol
rence to this current patient.\eol
\traceend}
\scomm
{{\TEIRESIAS} now invokes the performance program as a subprocess to make sure the
bug is fixed, and to test for any other side effects. Since {\sc MYCIN} has
saved all the answers from the initial consultation, the process is fairly
inexpensive. The expert is warned about new questions because his new rule
may mention an attribute that was not previously traced, or it may
indirectly cause the tracing of one.
\commpara
While there are some cases in which it is possible to compute the
incremental effect on a given consultation of adding a single new rule to
the knowledge base, these are rare enough that in the long run it is
computationally cheaper to simply rerun the consultation.}
\ecomm
{\tracebegin
\eol
18-DEC-75 16:30:46\eol
\eol
\ \ \ --------PATIENT-281--------\eol
\eol
\ \ \ \ \ \ --------INFECTION-1--------\eol
\eol
\ \ \ \ \ \ \ \ \ --------CULTURE-1--------\eol
\eol
\ \ \ \ \ \ \ \ \ \ \ \ --------ORGANISM-1--------\eol
\traceend}
\scomm
{The answers to all questions were available internally, so the performance
program asks nothing new. (The headings are printed to let the expert
follow the progress of the consultation.)}
\ecomm
{\tracebegin
\eol
My therapy recommendation will be based on the following\eol
probable infection(s) and potential causative organism(s):\eol
\eol
INFECTION-1 is PRIMARY-BACTEREMIA\eol
\ \ \ \ <Item\ 1>\ \ E.COLI\ [ORGANISM-1]\eol
\ \ \ \ <Item\ 2>\ \ KLEBSIELLA-PNEUMONIAE\ [ORGANISM-1]\eol
\ \ \ \ <Item\ 3>\ \ PROTEUS-NON-MIRABILIS\ [ORGANISM-1]\eol
\eol
\eol
Well, it appears that things are straightened out.\eol
\traceend}
\scomm
{The new conclusions are the ones the expert indicated earlier as the
correct answers. This does not go unnoticed by {\TEIRESIAS}, which, as before,
interrupts the consultation at this point to check the validity of the
answers produced.}
\ecomm
{\tracebegin
\eol
Are all these values correct now?\eol
++**{\bf Y}\eol
\traceend}
\scomm
{As always, {\TEIRESIAS} gives the expert the last word and waits for approval
before proceeding.}
\ecomm
{\tracebegin
\eol
Good, then the problem's been fixed.\eol
\ \ \ \ \ \ellipsis continuing with therapy selection now.\eol
\eol
\traceend}
\scomm
{At this point {\TEIRESIAS} allows the performance program subprocess to continue
with the normal therapy-selection phase. This has been omitted here for
brevity.
\commpara
The reader may be wondering why three errors disappeared with the
addition of one rule. This is explained schematically below:\par
\null{\tracebegin \eightpoint \rm
RULE116 **\eol
RULE050 **\eol
RULE383\ \ --->\ \ CATEGORY\ \ ---\ **\ RULE184\ **\ --->\ \ IDENTITY\ =\ \ PSEUDOMONAS-AERUGINOSA\eol
\eol
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ------\ RULE084\ ------>\ \ IDENTITY\ =\ \ KLEBSIELLA-PNEUMONIAE\eol
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ PROTEUS-NON-MIRABILIS\eol
\traceend}\null\sl\noindent
As before, 116 and 50 have failed (hence the **s), but now the new rule, 383, has
succeeded, supplying a value for category. In turn, 184 now
fails, as hoped, and thus no conclusion is made about pseudomonas-aeruginosa.
\commpara
However, rule 84, which requires a value of category and failed last
time because the system was unable to deduce one, can now
fire and yields the desired, missing identities.}
\ecomm
{\tracebegin
\eol
\ctrline{********************}\eol
\eol
\traceend}
\scomm
\index{ knowledge base management}{All of the bookkeeping that was
done is accessible via the {\bf INFO}rmation
command added to the question-answering facility of the performance program.
This gives the expert the background for any rule in the system.}
\ecomm
{\tracebegin
\eol
** {\bf INFO 383}\eol
\eol
RULE383\eol
-------\eol
\ \ was\ written\ by\ Dr.\ Davis\eol
\ \ on\ December\ 18,\ 1975\eol
\ \ for\ the\ following\ reason:\eol
\ \ \ \ \ \ \ \ \ \ \ \ THE\ SYSTEM\ FAILED\ TO\ REALIZE\ IT\ COULD\ CONCLUDE\ \eol
\ \ \ \ \ \ \ \ \ \ \ \ CATEGORY,\ AND\ THIS\ ALLOWED\ RULE184\ TO\ INCORRECTLY\eol
\ \ \ \ \ \ \ \ \ \ \ \ CONCLUDE\ IDENTITY.\eol
\eol
\ \ for\ patient\ 281\eol
\ \ \ \ \ \ \ [who\ was\ described\ as\ follows:\eol
\ \ \ \ \ \ \ \ \ \ \ \ CLASSIC\ CASE\ OF\ GRAM\ NEGATIVE\ ROD\ INFECTION\ FOR\ A\ \eol
\ \ \ \ \ \ \ \ \ \ \ \ PATIENT\ WITH A NON-NOSOCOMIAL DISEASE]\eol
\traceend}
\null\sectionskip
\sectionbegin[3]{Rule model overview}
\index{ knowledge acquisition in context}The utility of knowledge
acquisition in context should now be clear.
In this example we have seen how the availability of the contextual
information has made it much easier for the expert to specify the knowledge
required and how it has supported, as well, many of the ``intelligent''
actions taken by the program.
\index{ expectations}One of the uses of this contextual information is as a source of
expectations about the content of the expert's new rule. The concept of an
``expectation'' is precisely defined in {\TEIRESIAS}, and in order to provide some
perspective on its intellectual origins and development, we consider the
concept of {\sl models}\ffnote{The concept of a model has been an integral part of
science and philosophy for quite some time. The work described here can be
seen in terms of the standard definitions that have evolved, and it fits
quite easily into the frameworks that have been developed. Since the
literature on the subject is extensive, we will not deal with it here. For
a useful introduction, see [Harre70], especially chapter 2.} and\index{ model-based understanding}
{\sl model-based understanding}.
The use of models in computer programs as a guide to understanding
dates back to early efforts in AI. The author's first encounter with it was
in work on computer vision, and since this offers a particularly clear
introduction to the ideas involved, we digress for a moment to introduce
some useful concepts from that field. (The treatment here is necessarily
superficial. For a broader review of current work, see [Barrow75]; for an
interesting introduction to the capabilities of the human visual system,
see [Gregory66].)
\subsectionbegin[3.1]{Perspective: Model-Based Computer Vision}
\index{ computer vision}Computer interpretation of a scene typically starts with
digitization, in which the picture is turned into a large array of numbers
indicating the light intensity at each point. The task is then to
determine which physical objects in the scene produced each of the
different regions of intensity values in the array. Among the tools used
are various types of edge detectors. These are mathematical operators that
are sensitive to certain sorts of changes in the intensity level values,
usually sharp gradients or step functions, which suggest the end of one
region and the beginning of another.
One of the first significant stumbling blocks encountered in scene
understanding was the presence of shadows and noise.\ffnote{Noise can be
electronic, can be due to digitization effects, or can simply be the result
of smudges or dirt on the objects in the scene.} Real scenes rarely contain
all the detail seen (or interpreted) by the human eye/brain processor.
Many of the edges of objects, for instance, are lost in shadows; these same
shadows often suggest false edges as well. As a result, the uniform
application of an edge detector results in a large collection of ``edges,''
only some of which are real. It is in part because human vision is an eye
{\sl and} brain process that we are not similarly confused---we are able to
classify objects being viewed and, based on this classification, can ignore
false edges and supply missing ones.
Some of the first vision work to take these problems into account was done by
Falk [Falk70], building on the work of Roberts [Roberts63] and Guzman
[Guzman68]. The key elements of this work that are of interest here are\index{ models}
({\it i\/}) a set of {\sl prototypes} (or models) that {\sl embody knowledge}
about the objects being viewed and ({\it ii\/}) the use of these prototypes as
a way of {\sl guiding the process of understanding}.
Falk's system (like many others) viewed scenes containing a number
of children's blocks selected from a known set of possible objects. His
prototypes were similar to wire frame models of each of the blocks and thus
embodied a ``high-level'' description that indicated the structure of each
object. This compact, high-level description was then used to guide the
lower level processing of the intensity values. After detecting a number
of edges in the scene, his system attempted to fit a model to each
collection of edges and then used this model as a guide to further
processing. If, for instance, the model accounted for all but one of the
lines in a region, this would suggest that the extra line might be
spurious. If the model fit well except for some line missing from the
scene, this was a good hint that a line had been overlooked and also an
indication of where to go looking for it.
One other idea necessary to complete a general perspective on the
use of models to guide understanding is described quite well by a
distinction drawn in [Baumgart74]. As he points out (also in the context of
scene understanding, but it generalizes easily), three different approaches can
be identified:
\index{ verification}
\index{ description}
\index{ recognition}
\listbegin
\numlistentry[1]{{\sl Verification}. ``Top down'' or completely model-driven processing
concentrates on verifying the details in a scene about which much is already known.}
\numlistentry[2]{{\sl Description}. ``Bottom up'' or data-driven
processing involves searching an
unfamiliar scene for any suggestive features that might indicate what is present.}
\numlistentry[3]{{\sl Recognition}. ``Bottom up into a prejudiced top'' is
processing where there is available
some idea of what to expect, and where perhaps a small set of possibilities can be
specified, but none definitely. The data is allowed to suggest interpretations,
but the set of items to be considered is constrained to those expected.}
\listend
The first approach is useful when the contents of
the scene are known and when the task concerns only settling details of orientation
or precise location. The second can be used as the initial approach to an
unfamiliar scene, and the third is relevant if there is some idea of what is
present, but nothing definite. (Of course, all three might well be used on
the same scene at different points in the processing.)
Finally, note that one of the long recognized potential weaknesses of\index{ models}
a model-based approach is the dependence on a fixed set of models. Since the
scope of the program's ``understanding'' of the world may be constrained by the
number of models it has, ``\ellipsis it would be desirable [for a program] to be able to
`learn' new structural descriptions of models'' [Falk70].
\subsectionbegin[3.2]{Rule Models: Overview}
For rule acquisition the primary problem to be solved is the
interpretation of the new rule.
Note that this problem can be viewed as analogous to a
problem in perception: (a) There is a signal to be processed (text); (b)
the signal is noisy (``noise'' words that convey no information); and (c)
there is a large amount of context available (from tracking down the error)
on which to base expectations about the signal content. It would prove
useful, then, to have something analogous to Falk's prototypes, something
to capture the ``structure'' of the physician's reasoning, that would offer a
way of expressing expectations and guiding the interpretation of
his statement of the rule. In short, we are asking for the cognitive
analogue of the polyhedra prototypes.
But is it reasonable to expect that such structures exist? There
are several reasons why the idea seems plausible. Concepts in human
memory, for instance, are structured in an implicit, but highly complex
fashion. They rarely exist independently, but rather have a number of
cross references and interrelationships. New knowledge is typically ``filed
away,'' rather than just deposited, and it is clear when some new item
``doesn't fit'' into the established structure (see, \eg, [Norman75]).
There are also suggestive regularities in the set of rules in the
{\sc MYCIN} system. They were first noticed in a naive survey of the
knowledge base when the author began working with the system and were later
verified by a simple experiment which demonstrated that three of the
clinicians associated with the project each, independently, detected the same
regularities.\ffnote{Each of the clinicians was given a complete set of rules
and asked to sort them into ``similarity classes,'' subsets of rules
that seemed to belong together. The criteria for similarity were
purposefully left up to each clinician, who was asked to label each subset
to explain what kind of rules it contained. The results strongly confirmed
initial impressions---all the clinicians chose the same set of similarity
classes (except that some classes had occasionally been further
subdivided), and of 300 rules, there were substantial disagreements on the
classification of only six.}
The cognitive models will thus be based on uniformities in subsets
of rules and will look like abstract descriptions of those subsets, based\index{ empirical generalizations}
on a set of empirical generalizations about them. They are referred to as
{\sl rule models}. As will become clear, they represent a simple form of
concept formation---the concept of a ``typical'' rule in that subset. They
will be used to express expectations about the expert's new rule and to
guide processing of the English text.
Rule models are composed of four parts (Figure 5--1).
% .STARTFIG; TABS 25; TURN ON ''\'';
% %3EXAMPLES%* \the subset of rules which this model
% \describes
%
% %3DESCRIPTION%* \characterization of a ``typical'' member of
% \this subset
% \ characterization of the premise
% \ characterization of the action
% \ which attributes ``typically'' appear
% \ correlations of attributes
%
% %3MORE GENERAL%* \pointer to more general models
% %3MORE SPECIFIC%* \pointer to more specific models
%
% .FIG(Rule model structure,RMODELOVERVIEW:)
% .ENDFIG;
% .continue
\vskip 12pc \figtitle 5-1{Rule model structure.}
\noindent
They contain, first, a list of {\tt EXAMPLES}, the subset of rules from which
this model was constructed. Next, a {\tt DESCRIPTION} characterizes a
typical member of the subset. Since we are dealing in this case with
rules composed of premise-action pairs, the {\tt DESCRIPTION} currently
implemented contains individual characterizations of a typical premise and
a typical action. Then, since the current representation scheme used in
those rules is based on associative triples, we have implemented those
characterizations by indicating (a) the attributes that typically appear
in the premise (action) of a rule in this subset, and (b) the correlations
of attributes appearing in the premise (action).
Note that the central idea is the concept of {\sl characterizing a
typical member of the subset}. Naturally, that characterization would
look different for subsets of rules, procedures, theorems, etc. But the
main idea of characterization is widely applicable and not restricted to
any particular representational formalism.
The two other parts of the rule model are pointers to other models
describing more general and more specific
subsets of rules. The set of models is organized into a number of tree
structures, Figure 5--2. At the root of each tree is the model
made from all the rules that conclude about a given attribute (\eg, the
{\tt CATEGORY} model); below this are two models dealing with all affirmative
and all negative rules (\eg, the {\tt CATEGORY-IS} model); and below this
are models dealing with rules that affirm or deny specific values of the
attribute.
% .STARTFIG;TURN OFF ``\'';select boxfont;
% <attr>
% ≤ ≥
% ≤ ≥
% ≤ ≥
% ≤ ≥
% <attr>-is <attr>-isnot
% / \ / \
% / \ / \
% / \ / \
%
% <attr>-is-X <attr>-is-Y <attr>-isnot-X <attr>-isnot-Y
%
% .FIG(Organization of rule models, RMODELTREE:)
% .ENDFIG;
\topinsert{\vskip 9pc \figtitle 5-2{Organization of rule models.}}
For any given attribute, some of the branches may not exist since
we require (empirically) that there must be at least two relevant rules
before the corresponding model is created (which was why there was no
{\tt CATEGORY-IS-ENTEROBACTERIACEAE} model in the current system).
The fact that the models are organized around the contents of the
action part assumes that rules which conclude about the same thing have
useful similarities in their premises. This assumption was made plausible
by several considerations. To begin with, this organization paralleled the
one used by the clinicians when they were asked to sort the rules. It was
also hoped that the models would be more than just a description of a
subset of rules, that they might also suggest things about the reasoning process
itself. It is possible, for instance, that simple correlations among terms
in rules might actually reflect a valid generalization about the way an
expert reasons in this domain. In the current implementation, therefore,
the models are organized around the action part of the rule; but, as
discussed below, other organizations are possible.
Rather than being hand-tooled, the models are assembled by {\TEIRESIAS} on
the basis of the current contents of the knowledge base, in what amounts to
a very simple (\ie, statistical) form of concept formation. Thus, the
combination of {\TEIRESIAS} and the performance program presents a system that has a
model of its own knowledge, a model it forms by itself.\index{ model of knowledge}
\subsectionbegin[3.3]{Rule Models: Example}
Shown below is an example of a rule model from the current system.
This particular model describes the subset of rules that conclude
affirmatively about the category of an organism and is the one that was
used by the system in the trace shown earlier. Each of the pieces of the
model will be described in some detail, to give the reader a feeling for
the concepts involved. The usual warnings apply, however: It is the
global concepts that are important here, rather than the precise format or
location of every parenthesis. The models are also fairly compact, in the
sense that they contain a great deal of information. We will see that all
of it is used eventually.
% .STARTFIG;SELECT 6;TURN ON ''↓_'';
% ↓_CATEGORY-IS_↓
%
% EXAMPLES ((RULE116 .33)
% (RULE050 .70)
% (RULE037 .80)
% (RULE095 .90)
% (RULE152 1.0)
% (RULE140 1.0))
%
% DESCRIPTION
% PREMISE ((GRAM SAME NOTSAME 3.83)
% (MORPH SAME NOTSAME 3.83)
% ((GRAM SAME) (MORPH SAME) 3.83)
% ((MORPH SAME) (GRAM SAME) 3.83)
% ((AIR SAME) (NOSOCOMIAL NOTSAME SAME) (MORPH SAME)(GRAM SAME) 1.50)
% ((NOSOCOMIAL NOTSAME SAME) (AIR SAME) (MORPH SAME)(GRAM SAME) 1.50)
% ((INFECTION SAME) (SITE MEMBF SAME) 1.23)
% ((SITE MEMBF SAME) (INFECTION SAME) (PORTAL SAME) 1.23))
%
% ACTION ((CATEGORY CONCLUDE 4.73)
% (IDENT CONCLUDE 4.05)
% ((CATEGORY CONCLUDE) (IDENT CONCLUDE) 4.73))
%
% MORE-GENL (CATEGORY)
%
% MORE-SPEC NIL
% .WIDECAPFIG(Rule model for rules concluding affirmatively about category,RMODELEXAMPLE:);
% .ENDFIG;
\topinsert{\vskip 20pc \figtitle 5-3{Rule model for rules concluding affirmatively
about category.}}
This model was formed from the six rules listed in the {\tt EXAMPLES}
part of Figure 5--3. (The numbers between zero and one
associated with the rules are the relevant certainty factors from the
conclusions; these are used when updating the models in response to changes
in the knowledge base.)
The {\tt DESCRIPTION}s of the premise and action indicate
regularities found in the subset of rules listed in {\tt EXAMPLES}. The
two types of description noted above are each encoded in their own
format: There are ``singlets'' indicating which attributes typically appear
and ``ntuples'' indicating (empirical) correlations of attributes.
For instance, the first singlet in the premise description above
\centerit{(GRAM SAME NOTSAME 3.83)} indicates that gramstain ({\tt GRAM})
typically appears and is often associated
with the functions {\tt SAME} and {\tt NOTSAME}. (The 3.83 is explained
below.)
The third item in the premise description of Figure 5--3
is an example of an ntuple: \centerit{((GRAM SAME)(MORPH SAME) 3.83).}
It indicates that whenever gramstain appears
in a rule premise, morphology ({\tt MORPH}) is typically found as well.
A collection of this sort of information can provide a fairly
detailed picture of the ``typical'' appearance of a rule from this subset.
In this case, rules that conclude affirmatively about category ``typically''
mention gramstain and morphology; when one of these appears, the other
tends to appear also, and so on.
Finally, the {\tt MORE-SPEC} and {\tt MORE-GENL} pointers indicate that
there is no rule model more specific than this one in the current system
and that the {\tt CATEGORY} model is more general.
\subsectionbegin[3.3.1]{Details of the DESCRIPTION Implementation}
Each singlet is of the form
\centerit{( \<attrib> \<predicate-function>$↑+$ \<cf-sum> )}
where the superscript ``+'' indicates one or more of instantiations of the item. A singlet of this
sort will be constructed for any attribute that appears in the
premises of at least 30{\%} of the rules in the subset.\ffnote{This and all other
thresholds cited are purely empirical. They were chosen solely on the basis of
producing results that were similar to those suggested by the rule sorting
experiment performed with the clinicians.} Enough predicate functions are then
supplied to account for at least 75{\%} of the appearances of the attribute. Thus
the example cited above means that (a) gramstain occurs in a
premise clause of at least 30{\%} of the rules listed in {\tt EXAMPLES}, and (b)
75{\%} of those clauses containing gramstain use either {\tt SAME} or
{\tt NOTSAME} as the predicate function.
The 3.83 at the end is the sum of the certainty factors of the
rules that had premise clauses mentioning gramstain. As will become
clear, the {\tt DESCRIPTION}s contained in the rule models provide {\TEIRESIAS} with
``advice'' about what to expect to find in a newly acquired rule; in
these terms, the numbers become an indication of the ``strength'' of this
advice. While its origin is purely empirical, there are reasons why it
appears to be plausible. First, by summing up CFs, the strongest
advice will
arise from the factors that appear the most often. Since the
model is supposed to characterize the typical content of a rule, a
dependency of strength on frequency of appearance seems reasonable.
Second, rules with high CFs tend to be those that are the soundest and
perhaps the closest to being based on an understanding of underlying processes
rather than simply on experience. Thus, given equal frequency of appearance,
advice arising from more definite rules will be stronger. Finally, it
appears to give a satisfying range of strengths; in the
current system, the largest such value is close to 21, the smallest is
0.7.
To review, the first singlet in the rule model of
Figure 5--3 means that at least 30{\%} of the rules in
{\tt EXAMPLES} had a premise clause containing gram stain, that at least 75{\%}
of those clauses used either {\tt SAME} or {\tt NOTSAME} and, finally, that the
sum of the CFs of those rules was 3.83.
The general form of the ntuples is
\centerit{( (\<attrib> \<predicate-function>$↑+$)$↑+$ \<cf-sum> )}
and the first example in this model is
\centerit{((GRAM SAME) (MORPH SAME) 3.83).}
This ntuple means that whenever gram stain appeared in a rule premise,
morphology ({\tt MORPH}) also appeared at least 80{\%} of the time. The
implication is unidirectional---if it is also true that whenever
morphology appears, gram stain also appears (at least 80{\%} of the time),
then there would be another ntuple expressing this fact (as there is in this
case).\fnote{The interpretation of the \<predicate-function> and \<cf-sum> is
the same, except that the \<predicate-function>s are taken only from those
instances in which the \<attrib>s actually did appear together. This accounts
for the fact that {\tt NOTSAME} does not appear. Evidently, when gram and
morph appear together, they tend to use just {\tt SAME}.} All this generalizes
to more than two attributes so that, for example, the fifth element of the
{\tt DESCRIPTION} indicates that the presence of aerobicity ({\tt AIR})
indicates the likely presence of several other attributes.
\subsectionbegin[3.4]{Rule Models as Concept Formation}
\index{ concept formation}As noted, the rule models are constructed by {\TEIRESIAS} from the
rules in the performance program's knowledge base---the description of the
rule-model components given in the previous section is an informal
specification of the algorithm used.
Despite this automated construction, however, there are several
reasons why the rule models are only a weak form of concept formation.
First, and perhaps most important, the concepts are expressed in terms of a
predefined set of patterns: the singlets and ntuples, both used to describe the
fixed subsets of rules described in the previous section. While it would
not be difficult to add the ability to detect other types of patterns in
subsets organized along different criteria, this would not confront the
more fundamental problem of concept formation: the judicious selection of
the ``proper'' organization of the examples to detect ``important''
regularities and the ability to discover unpredicted patterns.
In addition, the current implementation commits what Winston calls
the ``fallacy that frequent appearance means importance'' [Winston70].
While the strength of each piece of advice in the models does provide some
measure of differential importance (similar to the ``must-have'' link in
[Winston70]), that measure is acquired purely on the basis of frequency.
This strongly limits the range of concepts that can be defined: There is
no way, for instance, to infer a link equivalent to a ``must-not-have'' link.
Nor is there any notion of {\sl why} a particular collection of attributes
tend to appear together. The current approach can not distinguish between
statistical accidents and a meaningful correlation. In the absence of a
carefully constructed set of teaching examples (in particular, there are
none of the ``near misses'' Winston uses to great advantage), the system uses
the only information it has and assumes that all rules in the knowledge
base are equally good instances.
Finally, the pattern detection routines all use an exhaustive
search of the knowledge base. This is not particularly sophisticated, and
a more powerful approach to concept formation should be more efficient.\ffnote{A
recent report [Hayes-Roth76] discusses more formal and efficient methods
for a similar sort of concept formation task.}
Despite the simplicity of the techniques used, the rule models
present an adequate picture of the concept of a ``typical'' rule. There are
several reasons why this is so. First, the concept is ill-defined to begin
with and is being formed from a very limited set of data. This implies
that it might not be wise to devote extensive amounts of computation to
sophisticated concept-formation routines. Second, the fundamental task
here is comprehension rather than concept formation, and the models are not
the end product of the program. The models are instead used later in a support
role to provide more sophisticated comprehension. Finally, exhaustive
search for patterns does not present significant problems because the
knowledge base is built incrementally, hence rule model computation can
proceed in parallel. (As long as intermediate results are kept for
reference, the incremental computation is not time consuming.)
Improvements could still be made in all of these areas, but the point here
is simply that very sophisticated techniques are not required for adequate
performance.
\subsectionbegin[3.5]{Implications}
A number of implications follow from the design and automated
construction of the models. First,
the use of the singlets and ntuples is really only one
instance of a more general idea. In fact, any kind of pattern involving
any of the components of a rule could be used. While they were not
included (for the sake of simplicity), patterns in the values of the
attributes or certainty factors might also have been considered.
Straightforward extensions to the current implementation would make it
possible to look for any specified pattern involving any of the components
and to use this in much the same way as a picture of what to expect in a
rule of this subset.
As noted, the rule models are assembled by the system from the
rules in the knowledge base. This automatic generation and updating has a
number of advantages.
In our discussion of Falk's original concept of models, for
instance, we noted both the potential disadvantage of a fixed set of models
and the utility of being able to add new models easily. The system
described here has avoided the disadvantage of a fixed set
and has the ability to add new models without difficulty. In addition:
\listbegin
\numlistentry[1]{The expert need never concern himself with adding models, since
{\TEIRESIAS} takes care of all the work involved. Indeed, the expert may
never know of the models' existence.}
\numlistentry[2]{{\TEIRESIAS} builds and updates the models on the basis of
{\sl experience}, a
capability that is intuitively appealing. Every time a new rule is added
to the knowledge base or an existing rule is modified, the appropriate model(s)
is recomputed.}
\listend
There are other implications as well.
It was noted above that the
model might be used to characterize many kinds of features displayed by the
rules. The correlation detection operators used to form the ntuples can be
viewed as demons, lying dormant until enough examples have accumulated to
trigger them, at which time they add their newfound correlation to the
appropriate model.
It was also mentioned above that the trees around which the models
are organized are quite often incomplete, since there may be too few rules
about a particular attribute. It should now be clear that this tree is
constantly growing (and shrinking), exactly paralleling the changes in the
knowledge base. The entire model set is thus kept current with the growing
knowledge base, evolving along with it, and reflecting the shifting
patterns it contains.
\index{ meta-level knowledge}The models are also one of the primary
examples of a central
theme of this work: higher level knowledge. While the rules are a
representation of (medical) knowledge, the models are a representation of
rules and, hence, are a representation of a representation. As
generalizations of a set of rules, they may suggest some of the
regularities in the structure of the reasoning embodied in the rules
in the knowledge base.
The models are also ``fuzzy.'' Just knowing that a rule concludes about a
particular attribute is insufficient information to completely specify
its premise, but it is enough to permit a number of plausible suggestions.
The representation thus requires a form of inexactness that allows the
specification of a range of possibilities, along with the likelihood of
each. The {\tt DESCRIPTION}s of premise and action offer this fuzziness.
There is also a certain ``critical mass'' effect. Early in the
construction of a knowledge base, there will be few models and their
advice will be somewhat unreliable, since the system is, in effect,
generalizing from too small a sample. As the knowledge base grows, the
system's own picture of its knowledge gets progressively better, trends
become more evident, and the models will make more effective contributions.
The way in which the models are used implies that the system will tend to
``hear what it expects to hear,'' and ``hear what it has heard before.'' This
will be explored in detail below, but note that it is not unlike the
typical human response in the same situation.
Perhaps most interesting, the presence of the models\index{ model of knowledge}
means that the system has a model of its own knowledge. As will become
clear further on, in a primitive sense it ``knows what it knows, and knows
where it is ignorant'' and, in a rudimentary way, can discuss both of these.
\sectionskip
\sectionbegin[3.6]{Character and Use of the Models}
Two further points remain to be made before reviewing the details
of the trace of system performance. First, recall that the design and use
of models was described in terms of three important facets:
They were to\index{ high-level description}\index{ expectations}
be a high-level description, they could be used to express expectations
about the world, and they could be used to guide interpretation and
``understanding.'' The role of rule models as high-level descriptions should
be clear from the previous discussion. The reader may by now have
recognized their use in expressing expectations: In the trace, after
narrowing down the source of the problem, {\TEIRESIAS} indicates that
\extractbegin\tt
I need a rule to deduce that the category of ORGANISM-1 \penalty-700 is
enterobacteriaceae.
\extractend
\noindent
This is both a set of instructions to the user about how to fix the problem
and an indication of the sort of rule the system will expect---it indicates
the rule model that will be employed.
\index{ description}The use of the models as a guide to understanding is the final
point. With the expectations that arise from doing acquisition in the
context of a shortcoming in the knowledge base, the system is not entering
the rule interpretation process blindly. In terms of the three
methodologies mentioned earlier, then, the {\sl descriptive} approach is
inappropriate. But the program should not be restricted to understanding
only rules that look like previous rules in the model, since the new ones
may be different from all previous examples.
It would thus be too\index{ verification}\index{ recognition}
inflexible to use a {\sl verification}-oriented approach, and the
{\sl recognition} technique appears to be just right. There are
expectations, but it is not certain that they will be fulfilled. Hence the
rule text is processed ``bottom up,'' but with a strong set of biases about
where that processing should eventually lead. In addition, the rule
models, like the polyhedra models, will be used to direct the processing of
the text and to help identify both noise and gaps in the signal.
\sectionskip
\sectionbegin[4]{How it all works}
At this point we begin the trace again, reviewing it piece by
piece, as a background for discussing some of the more interesting ideas in
{\TEIRESIAS} and as a way of exploring features not yet illustrated. To avoid the
necessity of flipping pages, the relevant sections of the trace have been
reproduced below, set off by horizontal lines.
It is both difficult and not particularly informative to attempt to
review all the options in the system, so only the more interesting examples
will be explored. In general, however, the proper facilities exist for
handling all cases, and short of purposeful attempts to supply inconsistent
answers, {\TEIRESIAS} takes the appropriate action.
For the sake of consistency, we will work with the single example
shown in the original trace. It is occasionally necessary, however, to illustrate
additional points by examining the system's action on hypothetical responses
from the user. These will be clearly indicated.
There are seven general phases to the rule acquisition process:
\listbegin
\numlistentry[(a)]{Tracking down the bug.}
\numlistentry[(b)]{Deciphering the English text of the new rule.}
\numlistentry[(c)]{Checking preliminary results.}
\numlistentry[(d)]{``Second guessing.''}
\numlistentry[(e)]{Final checkout.}
\numlistentry[(f)]{Bookkeeping.}
\numlistentry[(g)]{Rerunning the consultation.}
\listend
Each is reviewed in turn.
\subsectionbegin[4.1]{Tracking Down the Bug}
\epigraph{I will not be persuaded to leave off the chance of
finding out the whole thing clearly.}
\author{Sophocles}
\source{Oedipus the King, lines 1065--1066}
\epigraphend
\noindent
The performance program's diagnosis is used as an entry point to
the debugging routine. This is a logical evaluation point since most of
the consultation is aimed toward determining it. It is possible
that the diagnosis may be correct due to offsetting errors in the
course of the consultation. However, since the expert can
interrupt the consultation at anytime during the processing
to use the explanation and acquisition routines, we make the
plausible (but imperfect) assumption that if he got this far and the
diagnosis is correct, then everything else is correct also.
\null
{\tracebegin
My\ therapy\ recommendation\ will\ be\ based\ on\ the\ following\eol
probable\ infection(s)\ and\ potential\ causative\ organism(s):\eol
\eol
INFECTION-1\ is\ PRIMARY-BACTEREMIA\eol
\ \ \ \ <Item\ 1>\ \ E.COLI\ [ORGANISM-1]\eol
\ \ \ \ <Item\ 2>\ \ PSEUDOMONAS-AERUGINOSA\ [ORGANISM-1]\eol
\eol
Are\ all\ these\ identities\ correct?\eol
++**{\bf N}\eol
\eol
Are\ there\ any\ identities\ missing?\eol
++**{\bf\ \ Y}\eol
Which\ one(s)?\eol
++**{\bf\ \ KLEBSIELLA-PNEUMONIAE\ \ \ PROTEUS-NON-MIRABILIS}\eol
Are\ there\ any\ identities\ that\ shouldn't\ have\ appeared?\eol
++**{\bf\ \ Y}\eol
Which\ one(s)?\eol
++**{\bf\ \ PSEUDOMONAS-AERUGINOSA}\eol
\traceend}\null
\index{ focusing}The focusing process begins immediately, as the expert is required
to specify exactly why he doesn't like the diagnosis shown. There must
either be an inappropriate answer present;
one that is missing; or, as in
the current example, both.
\null{\tracebegin
Do\ you\ want\ to\eol
\ \ \ \ \ \ 1]\ track\ down\ the\ problem\ yourself,\ or\eol
\ \ \ \ \ \ 2]\ allow\ me\ to\ guide\ the\ debugging,\ or\eol
\ \ \ \ \ \ 3]\ ignore\ it\ for\ now\ and\ fix\ it\ another\ time?\eol
Type\ 1,\ 2\ or\ 3\eol
++**{\bf\ 2}\eol
\traceend}\null
\index{ human engineering}Alternative $\#$1 was explored in
chapter 3, and $\#$2 is reviewed here.
Alternative $\#$3 is part of the emphasis on human engineering. Since the
process of tracking down and fixing the bug is a substantive task, the
expert is given a chance to avoid it. If he takes this
option, the system reminds him to ``try to remember to fix it some time''
and (quietly) composes and sends a note to a bug-reporting file, giving the
case number and the list of incorrect or missing answers indicated by the
user. This file
is routinely examined by system programmers, who can either fix the
problem or simply make sure that it gets attention later.
\null{\tracebegin
We'll\ start\ with\ the\ PSEUDOMONAS-AERUGINOSA\ first.\eol
\eol
The\ following\ rules\ were\ used\ in\ deducing\ that\ the\ identity\ of\eol
ORGANISM-1\ is\ pseudomonas-aeruginosa\eol
\eol
\eol
RULE184\eol
-------\eol
Since\ [1.1]\ the\ category\ of\ ORGANISM-1\ is\ not\ known\eol
\ \ \ \ \ \ [1.2]\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg\eol
\ \ \ \ \ \ [1.3]\ the\ morphology\ of\ ORGANISM-1\ is\ rod\eol
\ \ \ \ \ \ [1.4]\ the\ aerobicity\ of\ ORGANISM-1\ is\ facultative\eol
\ There\ is\ weakly\ suggestive\ evidence\ (.3)\ that\ the\ identity\ of\eol
\ ORGANISM-1\ is\ pseudomonas-aeruginosa\eol
\eol
\eol
Is\ this\ rule\ correct?\eol
++**{\bf\ \ Y}\eol
Should\ its\ premise\ have\ failed\ for\ this\ case?\eol
++**{\bf\ \ Y}\eol
Which\ clause\ of\ the\ premise\ should\ have\ been\ false?\ [give\ $\#$]\eol
++**{\bf\ \ 1}\eol
\traceend}\null
\index{(|focus, in explanations|)}The last three questions
directed to the user demonstrate the methodical unwinding process that
forces criticism to be very specific. At each point, the expert must either
approve of the rules invoked and the values obtained or indicate which one was
in error and supply the correction. An analysis of the performance program's
control structure indicates that if the value of an attribute A is incorrect,
then (if S is the set of rules in the knowledge base that conclude about A)
either:
\listbegin
\numlistentry[(a)]{Some rule in S which was executed had an error in its
conclusion.}
\numlistentry[(b)]{Some rule in S was not executed and should have been
(either because of an error in its premise or because a clause of the
premise incorrectly evaluated to ``false'').}
\numlistentry[(c)]{Some rule in S was executed and should not have been (either because
of an error in its premise or because a clause of the premise incorrectly
evaluated to ``true'').}
\numlistentry[(d)]{The set S is incomplete, and one or more rules is missing.}
\listend
\noindent
The routines in {\TEIRESIAS} reflect this analysis and can account for all
error sources within the current control structure. Thus, had the expert
indicated that rule 184 was incorrect, he would have been invited to use
the rule editor to fix it. Had he indicated that it was correct and that
it was not inappropriately invoked, the assumption would have been that
there was a rule missing that concluded negatively about the presence of
pseudomonas-aeruginosa (the missing rule would offset the action of 184
and, hence, remove the inappropriate identity).
The possibility remains, however, that the framework itself may
break down some day. That is, the expert may claim that all the rules are
individually correct, that they were all executed correctly, that no rule
is missing, and yet the final answer is still incorrect. This is most
likely to come about as a result of the possible inapplicability in a new
domain of the performance program's control structure or certainty factor
mechanism. If the expert does indicate that none of the established
classifications of the problem is correct, {\TEIRESIAS} will indicate its inability
to help further and use the bug reporting mechanism noted above to make a
note of the problem.
In this case, however, the expert has indicated that the first
clause of rule 184 (``{\tt the category of the organism is not known}'')
incorrectly evaluated to ``true.'' The process continues from there.
\null{\tracebegin
No\ conclusions\ were\ reached\ concerning\ the\ category\ of\eol
ORGANISM-1.\eol
\eol
Should\ it\ have\ been\ possible\ to\ conclude\ a\ category?\eol
++**{\bf\ \ Y}\eol
\eol
Which\ one?\eol
++**{\bf\ \ ENTEROBACTERIACEAE}\eol
\eol
There\ were\ no\ rules\ successfully\ invoked\ in\ the\ attempt\ to\eol
deduce\ that\ the\ category\ of\ ORGANISM-1\ is\ enterobacteriaceae.\eol
\eol
The\ following\ (potentially\ applicable)\ rules\ were\ NOT\ executed\eol
because\ the\ starred\ [**]\ clause\ failed:\eol
\eol
\eol
RULE116\eol
-------\eol
If\ \ \ \ 1)\ the\ identity\ of\ ORGANISM-1\ is\ not\ known\eol
\ \ \ **\ 2)\ the\ gram\ stain\ of\ ORGANISM-1\ is\ not\ known\ **\eol
\ \ \ \ \ \ 3)\ the\ morphology\ of\ ORGANISM-1\ is\ not\ known\eol
\ \ \ \ \ \ 4)\ the\ site\ of\ CULTURE-1\ is\ csf\eol
\ \ \ \ \ \ 5)\ the\ infection\ is\ meningitis\eol
\ \ \ \ \ \ 6)\ the\ age\ (in\ years)\ of\ Albert\ Hall\ is\ less\ than\ or\eol
\ \ \ \ \ \ \ \ \ equal\ to\ .17\eol
then\ \ There\ is\ weakly\ suggestive\ evidence\ (.33)\ that\ the\eol
\ \ \ \ \ \ category\ of\ ORGANISM-1\ is\ enterobacteriaceae\eol
\eol
\eol
RULE050\eol
-------\eol
If\ \ \ \ 1)\ the\ morphology\ of\ ORGANISM-1\ is\ rod\eol
\ \ \ \ \ \ 2)\ the\ gram\ stain\ of\ ORGANISM-1\ is\ gramneg\eol
\ \ \ \ \ \ 3)\ the\ aerobicity\ of\ ORGANISM-1\ is\ facultative\eol
\ \ \ **\ 4)\ the\ infection\ with\ ORGANISM-1\ was\ acquired\ while\ the\eol
\ \ \ \ \ \ \ \ \ patient\ was\ hospitalized\ **\eol
then\ \ There\ is\ suggestive\ evidence\ (.7)\ that\ the\ category\ of\eol
\ \ \ \ \ \ ORGANISM-1\ is\ enterobacteriaceae\eol
\traceend}\null
Since the need to deal with large numbers of rules was anticipated,
the rule unwinding process is kept as constrained as possible. Before
displaying all the rules that might have concluded any value of category, the
expert is asked which category it should have been. Then, only rules that are
appropriate to his answer need be considered.
\null{\tracebegin
Are\ all\ these\ rules\ correct?\eol
++**{\bf Y}\eol
Should\ any\ of\ them\ have\ been\ successfully\ invoked?\eol
++**{\bf\ N}\eol
Is\ there\ a\ rule\ missing?\eol
++**{\bf Y}\eol
\eol
Ok,\ then\ I\ need\ a\ rule\ that\ would\ allow\ me\ to\ deduce\ that\ the\eol
category\ of\ ORGANISM-1 is enterobacteriaceae.\eol
\eol
Would you like to give me such a rule now?\eol
++**{\bf Y}\eol
Good\ellipsis\eol
\eol
\eol
The new rule will be called RULE383\eol
\ If:\ \ \ \ 1\ -\ \ {\bf\ THE\ PATIENT'S\ INFECTION\ IS\ PRIMARY-}\eol
\ \ \ \ \ \ \ \ \ \ \ \ \ {\bf\ BACTEREMIA}\eol
\ \ \ and\ \ 2\ -\ \ {\bf\ THE\ SITE\ IS\ ONE\ OF\ THE\ STERILE\ SITES}\eol
\ \ \ and\ \ 3\ -\ \ \eol
\ Then:\ \ 1\ -\ \ {\bf\ THERE\ IS\ EVIDENCE\ (.8)\ THAT\ THE\ CATEGORY\ IS}\eol
\ \ \ \ \ \ \ \ \ \ \ \ \ {\bf\ ENTEROBACTERIACEAE}\eol
\ \ \ and\ \ 2\ - \eol
\eol
This may take a few moments\ellipsis\eol
\traceend}\null
The problem has finally been tracked down and characterized with an
indication of exactly what sort of rule is needed. As noted earlier, this\index{ expectations}
characterization also serves the purpose of setting up {\TEIRESIAS}'s expectations
about the sort of rule it is about to receive. Since there is not
necessarily a rule model for every characterization, the system chooses the
model that matches most closely. This is done by starting at the top of
the tree of models and descending until either reaching a model of the
desired type or encountering a leaf of the tree. In this case, the process
descends to the second level (the {\tt CATEGORY-IS} model), notices that
there is no {\tt CATEGORY-IS-ENTEROBACTERIACEAE} model at the next level, and
settles for the former. This technique is used in several places
throughout the knowledge transfer process and, in general, supplies the
model that best matches the current requirements. Note that it can deal
with varying levels of specificity in the stated expectations. If, for
instance, the system had known only that it expected a rule that concluded
affirmatively about category, it would have descended just that far in the
model tree and looked no further.
\subsectionbegin[4.2]{Deciphering the English Text}
\index{ recognition}It was suggested earlier that interpreting the natural language
text of the rule can be viewed as a ``recognition'' process in which the
data are allowed to suggest interpretations, but
the system maintains
certain biases about which interpretation is likely to be correct. {\TEIRESIAS} does
this, generating all consistent interpretations of each line of English
text and then evaluating each interpretation in the light of the biases
expressed by the choice of a specific rule model. The interpretations
suggested by the text (data-driven, ``bottom up'' mode) are thus intersected
with the expectations (hypothesis-driven, ``top down'' mode) provided by the
debugging process.
The interpretation process works in a strictly line-by-line
fashion, processing each line of text independently. This method
is a source of
some deficiencies, some of which are trivially fixed, while others are
superficial manifestations of interesting and complex problems. Each of
them is discussed in subsequent sections below.
Deciphering the text occurs in four stages:
\listbegin
\numlistentry[(a)]{Preprocessing the text.}
\numlistentry[(b)]{Checking the rule model.}
\numlistentry[(c)]{Generating the set of plausible {\sc LISP} interpretations.}
\numlistentry[(d)]{Scoring the interpretations by reference to the rule model.}
\listend
As will become clear, our approach to natural language is very
simple, yet powerful enough to support the performance required. The
problem is made easier, of course, by the fact that we are dealing with a
small amount of text written in a semi-formal technical language, rather
than with large amounts of text in unrestricted dialog.
Even so, the problem of\index{(|knowledge sources, in rule acquisition|);}
interpretation is substantial. The source of {\TEIRESIAS}'s power and performance
lies in its use of a multiplicity of knowledge sources. These are listed
and described briefly below; their use is explored in more detail in the
sections that follow. Since much of the interpretation process can be
viewed in terms of forming hypotheses (interpretations) from a set of data
(the text), each knowledge source is also labeled in these terms.
\listbegin
\ctrline{Data-driven knowledge sources:}
\null
\numlistentry[1]{{\sl Connotations of individual words} (data interpretation).
As explained in more detail below, each English word may have
associated with it a number of connotations of varying strength. These
indicate attributes, objects, values, or predicate functions to which the
word may plausibly be referring.}
\numlistentry[2]{{\sl Degree of ambiguity of individual words} (ambiguity
of the data). This
is used to constrain the search for an interpretation of the text.}
\numlistentry[3]{{\sl Function template} (structure of the hypothesis). As noted in chapter 2,
there is associated with each predicate function a template indicating the
order and generic type of its arguments. Generating code is essentially a
process of filling in this template; it thus provides a primary source of
direction for the interpretation process.}
\numlistentry[4]{{\sl Degree of success of the template completion process} (degree of success
of hypothesis construction). The expert may be terse enough in his rule
statement that the contents of certain slots in the template must be
inferred rather than sought in the text. Such inferences are made with
different degrees of confidence.}
\index{ consistency}
\numlistentry[5]{{\sl Consistency of meaning assignment} (consistency of data interpretation). Where
ambiguity exists, several plausible interpretations of a clause
may arise; the appropriate bookkeeping is done to assure that each word is
understood in only one way for any given interpretation.}
\numlistentry[6]{{\sl Accounting for all words in the text} (accounting for all the
data). Preference is given to those interpretations that leave fewer words
unaccounted for in a line of text.}
\numlistentry[7]{{\sl Consistency of attribute, object, and value interrelationships} (internal
consistency of hypothesis structure). This is used in several ways. For
instance, in assembling an interpretation, ambiguity can sometimes be
resolved simply by restricting interpretation to syntactically valid
triples (\eg, there may be several attributes and values suggested by the
text, but perhaps only one of the possible pairings is syntactically
valid). Also, knowing one of the three may help guide the search for
another (\eg, if the attribute is known [or postulated], then {\TEIRESIAS} can refer
to it to determine the appropriate kinds of values to seek).}
\null
\ctrline{Expectation-driven knowledge sources:}
\null
\hddlistentry[{\sl The rule model}.]{As noted above, the model chosen during debugging is used
as a source of advice (or hints) about the possible content of the new rule.}
\listend
\subsectionbegin[4.2.1]{Terminology and Dictionary Structure}
The English version of a rule will be referred to as ``text,'' while each
of the components of the {\sc LISP} version will be referred to
as a ``{\sc LISP} clause.'' Thus {\sl the infection is primary-bacteremia}
is text, and the corresponding {\sc LISP} clause is {\tt (SAME CNTXT INFECTION
PRIMARY-BACTEREMIA)}. The terms ``parse'' or ``interpretation'' are used to mean
the creation of a single {\sc LISP} premise or action clause.
The natural-language-understanding capabilities are purely
keyword based. The connotation of a single word is determined by a number of
pointers associated with it.\ffnote{The current structure of the dictionary is the result
of work by a succession of people associated with the project, in addition to
the author.} These are, in general, inverse pointers
derived from the English phrases (``translations'') associated with many of the
data structures
in the system. For instance, a list like {\tt STERILESITES} has a
translation of {\sl those sites which are normally sterile.} As a result,
associated with the word {\sl sterile} is a pointer to the name {\tt STERILESITES}.
The creation and updating of these pointers are handled semi-automatically by
routines that help to minimize the bookkeeping task.
For ease of reference later on, the names of those pointers are
listed below, along with an indication of what they supply.
\nofill%
{\tt \<WORD1>}\rm
{\tt pointer value}\rm
{\tt INATTRIB }\rm\<word1> appears in the translation of these attributes
{\tt INOBJECT }\rm\<word1> appears in the translation of these object types
{\tt INFUNCS }\rm\<word1> appears in the translations of these predicate functions
{\tt VALUEOF }\rm\<word1> is a legal value of these attributes
{\tt INLTRANS }\rm\<word1> appears in the translation of these list names
\endnofill
\figtitle 5-4{Dictionary structure.}
\noindent
They are referred to collectively as ``connotation pointers.'' (There
are additional pointers to handle synonyms, but they are not relevant
here.) The important point is that the appearance of any given word can be
taken as evidence that the expert was talking about one of the attributes,
objects, predicate functions, values, or list names indicated by the
pointers for that word.
\subsectionbegin[4.2.2]{Pre-processing the Text}
The first step in processing the new rule is to take a single line
of text and replace each word with its root word equivalent. (Root words
provide a canonical form for plurals and other simple variations.) Common
words like {\sl a, and, the,} are explicitly marked in the dictionary as
content free, and are ignored.
All the connotations of each word are then obtained by referring to
the appropriate pointers. Figure 5--5 below shows the result of this
process.
As should be clear, this technique is strictly word by word. A
more sophisticated approach would have some grasp of grammar and would
attempt to assign meanings to entire phrases. We have been fairly
successful in spite of the primitive approach, primarily because of the
semi-formal nature of the technical language used: It tends to be terse,
relatively unambiguous, and has a high information content. {\TEIRESIAS} is thus
not often led astray by ambiguities or ``noise'' words in the text. The
common lack of correct grammar in the expert's responses also suggests that
any extensive or computationally expensive use of a grammar-based approach
might not pay off very well.
\null\nofill%
TEXT ROOT WORDS CONNOTATIONS
the the {\:s NIL}
patient's patient {\:s [NIL (INFECTION) (CURINF) NIL NIL]}
infection infection {\:s [NIL (INFECTION TREATALSO CYTOTOXIC}
{\:s NOSOCOMIAL WHENINFECT)}
{\:s (CURINF SUSPINF SUSPORG) NIL}
{\:s (ALLINFECTIONS)]}
is be {\:s [(SAME) NIL NIL NIL NIL]}
primary- primary-bacteremia {\:s [NIL NIL NIL (PRIMARY-BACTEREMIA) NIL]}
bacteremia
\endnofill
\figtitle 5-5{Original text, root words, and connotations. The connotations
are listed in the order: predicate function, attribute,
object, value, list name. Thus, {\sl patient} can be interpreted as an
indication of either an attribute or an object, while {\sl infection} has
numerous connotations.}
\subsectionbegin[4.2.3]{Checking the Rule Model}
{\TEIRESIAS}'s next step is to verify the applicability of the rule model
that was suggested by the debugging process (or supply a model, if it
``came in cold''). This is achieved by scanning each of the words in the
action part of the rule and checking their connotation pointers to see which
attributes or values are implicated.
If the debugging process has indicated which rule model to use, {\TEIRESIAS}
attempts to reconcile that model with the indications from the scan of the
action text. If there is agreement, nothing unusual happens. If, however,
it cannot reconcile any of the indications from the action text with the
given model, the system indicates this problem and asks the expert for
help. A trace of this process is shown below. Assume the system entered
as before, expecting a rule about category, but the expert suddenly thinks
of another rule he has been meaning to enter:
{\null\nofill\tt%
The new rule will be called RULE384
If 1 - {\bf THE ORGANISM IS A GRAMNEGATIVE ROD}
and 2 - {\bf IT IS ANAEROBIC}
and 3 -
Then: 1 - {\bf THE ORGANISM MIGHT BE A BACTEROIDES (.6)}
and 2 -
Hmm\ellipsis it seemed that this was going to be a rule to
deduce the category of a organism. But it doesn't appear to
be\ellipsis
To aid in analyzing this rule, please answer yes or no (Y or
N) to each of the following.
Is this a rule to deduce:
an organism or class of organisms for which therapy
should cover
** {\bf N}
a likely identity of an organism causing a infection
** {\bf N}
the identity of a organism
** {\bf Y}
Thank you\ellipsis
\endnofill\null}
\noindent
The important thing here is a fast and very simple checking process. The
first two incorrect guesses are the result of other connotations of the
word {\sl organism}. There are rarely more than four or five connotations in
any case, so even at worst,
the expert only sees a few bad guesses.
If the system had ``come in cold,'' the process would start at the
point where it says ``{\tt To aid in analyzing\ellipsis}'' Even without the debugging
process, then, all the benefits of the recognition-oriented approach are
still available.\ffnote{While modeling human performance was not one of our
motivations, it is interesting to note that both of these reactions are
similar to human behavior. Sudden changes in the topic of a conversation
can violate expectations about what is to follow, resulting in an
expression of surprise. Similarly, arriving in the middle of an ongoing
conversation often requires a moment to become oriented and prompts a
request for information. Elements of both of these are seen above.}
Once a model is selected, the interpretation process begins. As
indicated, it proceeds line by line and is oriented primarily toward doing
αthe best job possible with the limited natural language techniques
available. There are two important points to note. First, the system does
what might be called ``template-directed code generation,'' analogous to the
way English is often generated by ``filling in the blanks'' of a\index{ extended data type}
template.\fnote{The basic concept of filling in a template to generate code is
taken from the original design in [Shortliffe76]. All the rest of the
process that guides the template completion was designed by the author,
including the view of attributes, values, etc., as extended data
types.} Second, the system maintains several types of consistency in the
parses that it generates.
\subsectionbegin[4.2.4]{Generating a LISP Clause}
The next step is to generate the tree of possible parses. One
example of the generation process will serve to illustrate the important
ideas and explain what is meant by a tree of parses.\index{ tree of parses}
The process begins by determining which predicate function the
expert might have had in mind, scanning the list of connotations, and
choosing the predicate function that turns up most often. The template for
this function is retrieved, and the rest of the process of creating a
clause is guided by the attempt to fill in the template.\fnote{Note that
this is the same template described in chapter 2 as the basis for
the system's ability to dissect a rule.}\fnotepara{It has recently been
pointed out to me that the techniques used to fill
in the template are similar to some of the work on natural language parsing using
case grammars (see, \eg, [Rumelhart73]).} For example, suppose the
function is {\tt SAME} and the template is
\centerit{(SAME CNTXT ATTRIB VALUE)}
Associated with each of the primitives in the high-level ``language''
is a routine that embodies much of the semantics of each primitive. The
template is filled in by calling each routine as needed and allowing it to
examine the list of connotations to find the kind of object it requires.
Consider the text from the first line in the trace, {\sl the patient's
infection is primary-bacteremia}. The routine for {\tt VALUE} would
discover that the only object of type {\tt VALUE} suggested by the text was
{\tt PRIMARY-BACTEREMIA}. The routine for {\tt ATTRIB} would find several
objects of type {\tt ATTRIBUTE}, since the word {\sl infection} has a
large number of connotations. However, since the {\tt VALUE} routine has
already filled in {\tt PRIMARY-BACTEREMIA} as a {\tt VALUE}, this narrows the
choice to those attributes for which {\tt PRIMARY-BACTEREMIA} is a legal
value, and the routine takes the first of them ({\tt INFECTION}) initially.
The routine for {\tt CNTXT} notices that {\sl patient} can be interpreted as an
object,\ffnote{Recall that objects are also referred to as ``contexts,'' for historical
reasons.} one that is a valid object for the attribute {\tt INFECTION}, and
hence marks it as such. It returns the literal atom {\tt CNTXT}, reflecting
the fact that {\tt CNTXT} plays the role of a free variable that is bound
when the rule is invoked.
This produces the clause\fnote{Since the clauses are later scored for
likely validity, the first clause generated is not necessarily the system's
first guess.}\centerit{(SAME CNTXT INFECTION PRIMARY-BACTEREMIA)}
All the nontrivial words in the text have been assigned a meaning, so no
more clauses can be derived from it. There are, however, alternate
interpretations for two of the words ({\sl patient} and {\sl infection}). The\index{ backtracking}
system uses a standard depth-first search with backtracking and, at this
point, undoes its current set of meaning assignments and tries all the
alternatives. Other clauses are generated as alternate interpretations.
It will be instructive to examine one type of failure that can
occur as clauses are generated. This will illustrate the point made in
chapter 2, that knowledge acquisition is based in part on giving the system
access to and an ``understanding'' of its own representations. To see this,
consider the system's response to a line like {\sl the site of the culture is
blood}. The system will generate several clauses, including the correct
one (which uses {\tt SAME} as the predicate function and interprets {\sl culture}
as the object, {\sl site} as the attribute, and {\sl blood} as the value). In
one of its later attempts to construct other clauses, it will discover it has
used all the {\tt VALUE}s it can find, and the {\tt VALUE} routine thus fails.
The routine for {\tt ATTRIB} then finds it has not yet tried to interpret
{\sl culture} as an indication of the attribute ``{\tt the number of cultures in
this series}'' ({\tt NUMCULS}) and makes this assignment. It then invokes
the {\tt VALUE} routine with instructions to look for a value for
{\tt NUMCULS}.\fnote{The {\tt VALUE} routine can be re-invoked, despite its previous
failure, because there are a number of cases in which the word-by-word
approach fails. It is then profitable to go back and take another look as
long as there is some idea of what to look for. For attributes which are
either true or false, for instance, an indication of the {\tt VALUE} rarely
appears explicitly in the text (\eg, the text might be {\sl the patient is a
compromised host} rather than {\sl it is true that the patient is a
compromised host}).} That routine, in turn, uses its knowledge of the
structure of an attribute to examine {\tt NUMCULS}, discovers that it takes
an integer between 1 and 15 as a value, and finds none in the text. The
attempt to interpret {\sl culture} as an indication of {\tt NUMCULS} thus
fails, the assignment is undone, and the next alternative is tried.
Maintaining the internal consistency of the clauses generated is thus based
in part on giving the system the ability to examine its own
representations; in this case, an attribute is examined to find
out what kind of values are associated with it.
As may be clear, the template parts are not necessarily filled in
the order in which they appear in the template. The {\tt VALUE} part (if there is
one) is always tried first, for instance, since words indicating values in
this domain are often totally unambiguous.\ffnote{They are also sufficiently
strong clues as to text content that the {\tt ATTRIB} routines will supply
the attribute which belongs with a given {\tt VALUE}, even if no other
indication of that attribute can be found. This is what allows the system
to parse something like {\sl the organism is a gramnegative rod}, even though
there are no other indicators of gram stain (other than the value
{\sl gramnegative}) or morphology (other than the value {\sl rod}).} This
simple ``first pass'' strategy is built into the driver routines, but, since
one routine may invoke another, the order may soon become more complex.
The entire tree of parses is generated using the depth-first search
with the backup noted earlier. The result is a tree of clauses of the sort
shown below (part of the tree generated from the first line of text is
shown). At each node of the tree is a potential premise clause, and any\index{ consistency}
single path through the tree from the root to a leaf is a set of consistent
interpretations.
% .STARTFIG;SELECT 6
% /\
% / \
% / \
% / \
% / \
% / \
%
% (SAME CNTXT INFECTION PRIMARY-BACTEREMIA) (SAME CNTXT TREATALSO PRIMARY-BACTEREMIA)
%
% / \
% / \
% / \
% / \
% / \
%
% (SAME CNTXT CYTOTOXIC) (SAME CNTXT NOSOCOMIAL)
% .ENDFIG;xgenlines←xgenlines+1;
\topinsert{\vskip 13pc \figtitle 5-6{}}
Generation of the tree with alternative word meanings in
different branches provides the notion of consistency between
interpretations. Consistency is required in order to permit {\TEIRESIAS} to get more than
one {\sc LISP} premise clause from a single line of text without making
conflicting assumptions about that text. The current implementation takes
care of the most obvious sources of such conflicts by insuring that only
one meaning is chosen for each word.
There are a number of factors that prevent the tree of parses from
becoming unreasonably large. To explain the first factor, it is necessary
to refine the statement above which claimed that, in choosing a predicate
function, the first one chosen is ``the one that turns up most often.'' More
precisely, when choosing a predicate function (or any item to fill in one
of the blanks), the first one chosen is ``the one that turns up most often,
{\sl and} was suggested by unambiguous words.'' This means that the tree is
generated far more efficiently, with less backup. An example is
shown below, in two versions of a fragment of a parse tree that would
result from the text {\sl the organism is an aerobic rod}. {\sl Aerobic} is
ambiguous (it can be either an aerobicity value or an organism subtype),
while {\sl rod} is unambiguously a morphology value.
% .STARTFIG;TURN OFF ''\''; BOXFIG;
% / \
% / \
% / \
%
% (SAME CNTXT SUBTYPE AEROBIC) (SAME CNTXT AIR AEROBIC)
%
% | |
% | |
%
% (SAME CNTXT MORPH ROD) (SAME CNTXT MORPH ROD)
%
% .FIG (Inefficient tree of interpretations);
%
%
% |
% |
% |
%
% (SAME CNTXT MORPH ROD)
%
% / \
% / \
% / \
%
% (SAME CNTXT SUBTYPE AEROBIC) (SAME CNTXT AIR AEROBIC)
%
% .FIG (More efficient tree of interpretations);
% .ENDFIG;
\topinsert{\vskip 5pc \figtitle 5-7{Inefficient tree of interpretations.}
\vskip 5pc \figtitle 5-8{More efficient tree of interpretations.}}
Second, the insistence on consistency within a parse is simple but
very effective. It is more efficient to avoid producing invalid parses
than to generate them and prune them out later.
Finally, and perhaps most important, there is a very small amount of
text and most of it is relatively unambiguous. While the expert is
permitted to type an arbitrary amount in each text line, there are
typically no more than 15 or so words.
At this point the system has generated a tree of interpretations
for a single line of text. Any path in that tree from root to leaf
represents a consistent and plausible set of {\sc LISP} clauses that
contain all of the meaning that could be found in the text.
As each clause is completed, it is given a preliminary score that
reflects how it was assembled. For instance, those clauses for which
independent evidence was found for both {\tt VALUE} and {\tt ATTRIB} are given
the highest score. If the {\tt ATTRIB} must be implied by the presence of a
value, the score is somewhat lower. There are a number of other criteria
that are also used in composing the score. The main idea is simply to
provide some measure of how strongly the data (the text) suggested the
interpretations (the {\sc LISP} clauses) that were made.
\subsectionbegin[4.2.5]{Scoring the Parses}
The next step is to select a single interpretation for the text by
choosing a path through the tree of clauses. This is done
with reference
to the rule model chosen during the debugging phase. Each path is scored
according to how well it fulfills the expectations expressed by the model.
The singlets in the model predict the appearance of clauses containing
specific attributes and predicate functions, while the ntuples
predict the appearance of associations of clauses containing certain attributes.
The score for each path is the sum of the strengths of the
predictions that it fulfills.
There are thus two scores. The individual score for a given
{\sc LISP} clause indicates how strongly the clause was suggested by
the English text. The score for an entire path indicates how well the set
of clauses meets expectations.
These two are combined in a way that\index{ expectations}\index{ recognition}
emphasizes the expectations (the recognition-oriented approach), and
candidates are ranked according to the outcome. The system will thus ``hear
what it expects to hear'' if that is at all possible; otherwise, it will
choose the best alternative interpretation.
\subsectionbegin[4.3]{Checking Results}
\epigraph{May I say what I think second best? If there's a third best, too,
spare not to tell it.}
\author{Sophocles}
\source{Oedipus the King, lines 282--283}
\epigraphend
\noindent
Having chosen a likely interpretation for each line of text
typed by the expert, the system displays the entire rule and asks for
approval.
{\null\nofill\tt%
This is my understanding of your rule:
RULE383
-------
If: 1) Primary-bacteremia is an associated infection for
which therapy should cover, and
2) The infection with the organism was acquired while
the patient was hospitalized, and
3) The culture was taken from a sterile source, and
4) The organism is not normally found at this site
Then: There is strongly suggestive evidence (.8) that the
category of the organism is enterobacteriaceae
Okay? (Yes or No)
--**{\bf N}
\endnofill\null}
When the expert indicates a problem, the system invokes a rule editor
that allows him to make changes. He can add a clause (the system prompts for a
new line of text), delete one, undo a deletion (``undeleting''), or ask to change
a clause.
{\null\nofill\tt%
Change premise?
--**{\bf Y}
What should be changed in premise? (type HELP for list of
commands)
++**{\bf CHANGE 1}
Suppose (1) were changed to read-
1 - The infection is primary-bacteremia
Would that be ok?
++**{\bf Y}
Then you'll probably want to delete:
2) The infection with the organism was acquired while
the patient was hospitalized.
Correct?
++** {\bf Y}
\endnofill\null}
The ``change'' command makes use of the fact that
all the alternative interpretations of each text line have been saved. Given a clause
to be changed, the system invokes several heuristics to find the next most likely
interpretation. The primary heuristic is to examine the clause for a component
(a predicate function, attribute, value, etc.) that was suggested by
an ambiguous word in the text, to see if there is an alternative clause that
uses one of the other connotations of that word. The system thus tries to
reinterpret by making the smallest change it can, acting on the assumption that
the original clause is probably close to correct. If this fails, the clause
with the next highest overall score is chosen.
The alternatives are presented one by one for approval. If none
of them is acceptable, the system prompts for a new line of text. There are two
reasons for showing all the current alternatives before asking for new text.
First, the selection of an alternative is very fast, because all necessary data
structures are already present. Reprocessing a new line of text would take much
longer. More important, however, the expert gets a good idea of what he might
have said that triggered the system's incorrect interpretations
and can then rephrase
his statement appropriately. This can become important if there are only subtle
differences in the translations of several functions, attributes, etc.
This segment also demonstrates the utility of even the very limited form\index{ consistency}
of consistency checking that is available. {\TEIRESIAS} maintains a record of the tree of
parses, and whenever a clause is changed by selecting an alternative, it checks
to make sure that the new alternative is consistent with all the other clauses
derived from the same line of text. Once again, the process is very fast, since
all the data structures already exist.
{\null\nofill\tt%
Anything else?
++**{\bf D 3}
clause(s) 3 deleted.
Anything else?
++**{\bf ?}
1 - the infection is primary-bacteremia
and 2 - <deleted>
and 3 - <deleted>
and 4 - the organism is not normally found at this site
Anything else?
++**{\bf U 3}
clause(s) 3 undeleted.
\endnofill\null}
No deletions are actually done until exiting from the editor,
making it possible to undo mistaken deletions.
{\null\nofill\tt%
Anything else?
++**{\bf D 4}
clause(s) 4 deleted.
Anything else?
++**{\bf C 3}
Suppose (3) were changed to read-
3 - The site of the culture is one of: those sites
that are normally sterile
Would that be ok?
++**{\bf Y}
Anything else?
++**{\bf ?}
1 - the infection is primary-bacteremia
and 2 - <deleted>
and 3 - the site of the culture is one of: those sites that
are normally sterile
and 4 - <deleted>
++**{\bf OK}
Change action?
--**{\bf N}
This is my understanding of your rule:
RULE383
-------
If: 1) The infection is primary-bacteremia, and
2) The site of the culture is one of: those sites
that are normally sterile
Then: There is strongly suggestive evidence (.8) that the
category of the organism is enterobacteriaceae
Okay? (Yes or No)
++**{\bf Y}
\endnofill\null}
After making all the changes that the expert wanted, the system again
displays the rule and asks for approval. This time the expert is satisfied
with the interpretation.
This segment of the trace also displays one weakness of the current
implementation: Efficient use of the rule editor requires a familiarity
with the nature of the mistakes produced by the natural language routines.
Since all four lines of the system's original interpretation are incorrect,
the command ``CHANGE 1 2 3 4'' seems plausible. It takes a certain level of
familiarity with {\TEIRESIAS} to realize that clauses 1 and 3 are close but
incorrect, while 2 and 4 are purely spurious. While the expert need not
understand how the natural language routines work, and might acquire the
necessary sophistication through experience, the nontransparency of this
part of the system still presents a problem, and is
a likely topic for future work.
\subsectionbegin[4.4]{Second Guessing}
\epigraph{Do you know what you are doing? Will you listen to words to answer
yours, and then pass judgment?}
\author{Sophocles}
\source{Oedipus the King, lines 543--544}
\epigraphend
\epigraph{So clear in this case were the oracles; so clear and yet false.}
\author{Sophocles}
\source{Oedipus the King, lines 722--723}
\epigraphend
\index{ second guessing}Now that the expert has indicated
that the interpretation of his
text is correct, {\TEIRESIAS} double-checks the rule. The basic idea is to use the rule
model to see how well this new rule ``fits in'' to the system's model of its
knowledge, that is, does it ``look like'' a typical rule of the sort expected?
The point here is to take advantage of several unique characteristics of the
``student'' being tutored: {\TEIRESIAS} has ``total recall'' of every rule in the knowledge base
and has a great capacity for dealing with large amounts of detail. Both
of these characteristics are put to use in constructing the rule models.
Since the expert may be expressing rules that have never
previously been formalized, any help that the system can offer will prove very
useful. The models help by providing a basis for suggesting details that may
have been overlooked. In doing so, they also give the expert a hint of the ``world
view'' implicit in the rules already in the knowledge base.
\index{ partial match}The presence of a partial match between the new rule and the generalizations
in the rule model trigger a response from the system. Recall the last
ntuple of the premise description in the rule model of Figure 5--3:
\centerit{((SITE MEMBF SAME) (INFECTION SAME) (PORTAL SAME) 1.23))}
This means that when culture {\tt SITE} appears in the rule, {\tt INFECTION} type
and organism {\tt PORTAL} often appear as well. The new
rule has the first two but lacks the last, and the system points this out:
{\null\nofill\tt%
I hate to criticize, Dr. Davis, but did you know that most rules about what the
category of a organism might be, that mention-
the site of a culture
the infection
ALSO mention-
[A] - the portal of entry of a organism
Shall I try to write a clause to account for [A] ?
++**{\bf Y}
How about-
[A] The portal of entry of the organism is gi
Ok?
++**{\bf Y}
\endnofill\null}
Since the expert has agreed to a clause about portal of entry, the
system constructs it. The predicate function ({\tt SAME}) is supplied by the
ntuple. The template for {\tt SAME} is then completed in the usual way,
except that the system first checks in the record of the consultation. In
this case, it needs a {\tt VALUE} for {\tt PORTAL}, which is available as the
answer to question 18, asked during the consultation (Section 3--10).
Nothing further is needed, so the system requests
no assistance. (Had the desired information not been available---as would
be the case if it had ``come in cold'' rather than from the consultation---the
expert would have been asked to supply whatever was needed.) The result is a
plausible guess, since it insures that the rule
will in fact work for the\index{ knowledge acquisition in context}
current case (note the further use of the ``knowledge acquisition in context''
idea). It is not necessarily correct, of course, since the desired clause
may be more general, but it is at least a plausible attempt.
{\null\nofill\tt%
Also, most rules about what the category of a organism might be ALSO conclude about-
[A] - the identity of a organism
Shall I try to write a clause to account for [A] ?
++**{\bf N}
\endnofill\null}
There are also ntuples (in the description of the action) that
indicate patterns in the action of the rule, and one of these is applicable
to the new rule. As always, the expert can override the system's
suggestions, and does so in this case.\comment{The second epigraph used to
be here...}
It should be noted that there is nothing in this concept of ``second
guessing'' that is specific to the rule models as they are currently
designed, or indeed to the rules as a knowledge representation. The most
general and fundamental point is that mentioned above, of testing to see
how something ``fits in'' to the system's model of its knowledge. At this
point, the system might perform any kind of check, for violations of any
established prejudices about what the new chunk of knowledge should look
like. For rules, these checks might concern the size of its certainty factor,
the number of clauses in the premise, etc., in addition to the current
checks. Checks used with, say, a procedural encoding might involve the number and
type of arguments passed to the procedure, the use of global variables,
the presence of side effects, etc. In that case, for example, we can imagine
adding a new procedure to a system that then responds by remarking
``\ellipsis{\sl most procedures that do hash-table insertion also have the side
effect of incrementing the variable {\tt NUMBERELEMENTS.} Shall I add the code
to do this?''} In general, this ``second guessing'' process can involve any
characteristic that the system may have ``noticed'' about the particular
knowledge representation in use.
\subsectionbegin[4.5]{Final Checkout}
Now that both the expert and {\TEIRESIAS} are satisfied, there is one final
sequence of tests to be performed, reflecting once again the benefit of
knowledge acquisition in context.\index{ knowledge acquisition in context}
At this point, {\TEIRESIAS} examines several things about the rule, attempting
to make sure that the rule will, in fact, fix the problem uncovered. In this
case, for instance, the action of the new rule should be a conclusion about
category; the category mentioned should be enterobacteriaceae, and the
conclusion should be affirmative. The premise should not contain any
clauses that are sure to fail in the context in which the rule will be
invoked. (Note that these tests require the ability to dissect and
partially evaluate the rule, and they rely heavily on the use of the function\index{ partial evaluation}
templates to guide that dissection.) All of these are potential sources of
error that would make obvious the fact that the rule will not
fix the bug.
The new rule in the current example passes all these tests, but
note what would have happened if the user had (accidentally) typed
initially {\sl the site is {\bf not} one of the sterile sites}. Everything
would have been the same up until this point, when the following exchange
would have occurred.
{\null\nofill\tt%
The rule now reads:
RULE383
-------
If: 1) The infection is primary-bacteremia, and
2) The site of the culture is not one of: those sites
that are normally sterile, and
3) The portal of entry of the organism is gi
Then: There is strongly suggestive evidence (.8) that the
category of the organism is enterobacteriaceae
Sorry, but this rule won't work. In the context of
ORGANISM-1, clause 2 (``the site of the culture is not one of:
those sites that are normally sterile'') is sure to fail.
Would you like to change the rule?
++**
\endnofill\null}
The expert then has the option of either editing the current rule
or writing an entirely new one (since the current rule may be correct, only
inapplicable to the current problem). If he edits it, the tests are run
again, until the system is satisfied that there is nothing obviously wrong
with the rule.
\subsectionbegin[4.6]{Bookkeeping}
There are a number of straightforward bookkeeping tasks to be
performed. Some of them involve hooking the new rule into the knowledge
base so that it is retrieved and invoked appropriately. {\TEIRESIAS} does this by
scanning the clauses of the action part and adding the rule number to the
proper internal lists (\eg, in this case, it adds the rule number to the list of
rules that conclude about {\tt CATEGORY}.) This task is not difficult
because meta-rules can be used to express all necessary ordering of rule
invocation (see chapter 7). As a result, the lists can be stored
unordered, so adding a new rule to them is easy. All of this is taken care
of without assistance from the user.
\index{ knowledge base management}Another of the bookkeeping tasks involves tagging the rule with
information which facilitates maintaining the large and constantly
changing body of rules. Each rule is tagged with the name of the author,
the date of creation, the case number that prompted its creation (if there
is one), and the user's own comments on why he added (or changed) the rule.
This last item gives the expert a way of recording the reasons for any
rules or parts of rules that are not obvious. Since the rule in this
example is fairly straightforward, so are the user's comments.
{\null\nofill\tt%
Please describe briefly why you added (or changed) this rule.
[Type an empty line when done.]
**{\bf THE SYSTEM FAILED TO REALIZE IT COULD CONCLUDE CATEGORY,}
**{\bf AND THIS ALLOWED RULE184 TO INCORRECTLY CONCLUDE }
**{\bf IDENTITY.}
**
RULE383 has now been added to the knowledge base.
\endnofill\null}
It should be noted that rule 383 gets added only to the current
``working'' knowledge base. All
changes made by any individual are stored away at the end of the session,
filed under the individual's name. When the expert signs on again, the system
automatically searches for a file of the proper name and asks if the
changes should be reinstated. This allows each expert to build
up a knowledge base that includes his own personal preferences and yet
does not cause problems with maintaining a standard, functioning system for
other users. Permanent changes to the performance program knowledge base
are made after agreement from the experts.
At this point, the system also performs any necessary recomputation
of rule models.\ffnote{The models are recomputed when any change is made to the
knowledge base, including rule deletion or modification, as well as
addition.} The operation is very fast, since it is clear from the action
part of the rule which models may need to be recomputed, and the
{\tt EXAMPLES} part supplies the names of the other relevant rules. Note
that this means that {\TEIRESIAS}'s model of the knowledge base is kept constantly
up-to-date, immediately reflecting any changes. As a result, performance
on the
acquisition of subsequent rules may conceivably be better.
Since the updated rule models are filed away with the other changes, this
also means that the system will again reflect the ``structure'' of this
expert's reasoning the next time he logs in.
\subsectionbegin[4.7]{Rerunning the Consultation}
{\TEIRESIAS} then invokes the performance program as a subprocess,
rerunning the consultation to insure that additional effects of the new
rule are discovered. To do this, {\TEIRESIAS} first erases everything from the database
except the expert's responses to questions asked during the original
consultation. When the consultation is rerun, the information-requesting
routines look in the database for answers before asking the expert.
In this case, the single new rule has repaired all the problems.
\sectionskip
\sectionbegin[5]{Other Uses for the Rule Models}
There are other applications of the rule models
that help to characterize their role in allowing the system to ``know
what it knows,'' and which make plausible the claim that they indicate useful
regularities in the knowledge base.
\lsubsectionbegin[5.1]{``Knowing What You Know'': Rule Models}{as Abstract
Descriptions of Knowledge}
The rule models have also been integrated into the question-answering
program that is part of {\sc MYCIN}.
Previously, {\sc MYCIN} would respond to a question like {\sl How do you determine
the identity of an organism?} by typing out the names of all the relevant
rules and asking which the user wanted to see. But a rule model, as a
generalization of an entire class of rules, answers the question too.
{\null\nofill\tt%
** {\bf HOW DO YOU DECIDE THAT AN ORGANISM IS
PSEUDOMONAS AERUGINOSA?}
Rules which conclude that the identity of the organism is
pseudomonas-aeruginosa generally use one or more of the
following pieces of information:
the site of the culture
the gram stain of the organism
the morphology of the organism
Furthermore, the following relationships hold:
The gram stain of the organism and the morphology of the
organism tend to appear together in these rules.
RULE184, RULE116, RULE047, RULE085, and RULE040 conclude that
the identity of the organism is pseudomonas-aeruginosa.
Which of these do you wish to see?
**
\endnofill\null}
\noindent
By simply ``reading'' the rule model to the user, the system first supplies
an overview of the knowledge in the relevant rules and then allows the user
to examine any of those rules for specific details. This overview suggests
the structure of global trends in the knowledge of the experts who
assembled the knowledge base and thus helps to define the overall approach
to any given topic.
\subsectionbegin[5.2]{``Knowing What You Don't Know''}
There are models in the current system made from between
2 (the defined minimum) and 35 rules. We have defined a metric to measure
the ``strength'' of a model and have based it on both the total number of rules from
which the model was constructed and the size of the CF for each of those
rules.\ffnote{In more detail: Model M1 is ``stronger'' than model M2 (a) if M1 was
constructed from more rules than M2, or (b) when the number of rules in both is the
same, if the sum of the certainty factors of the rules from which M1 was made
is larger than the corresponding sum for M2.}
The entire model set is kept ordered from weakest to strongest, giving the
system some indication of its likely competence on a range of subjects. In a
very primitive way, it thus gains a knowledge of where it is ignorant.
This feature
makes possible a new option for the expert. Instead of adding a rule
to fix a bug, he can ask the system what it would like to learn. (There is
currently no
real language processing done on the question below; the system checks
for precisely the sequence of words shown.)
{\null\nofill\tt%
--** {\bf WHAT WOULD YOU LIKE TO KNOW?}
There are only 2 rules for concluding that the identity of a
organism might be enterococcus. Would you like to give me a
rule for that?
++** {\bf N}
There are only 2 rules for concluding that a infection might be
infective-endocarditis. Would you like to offer a rule for
that?
++** {\bf Y}
The new rule will be called RULE384
If 1-
\endnofill\null}
\noindent
The system cycles through the rule models in order, indicating the weakest
topics first. The current implementation ignores topics for which no rule
models exist. It also makes the (imperfect) assumption that subjects for
which there are no rules at all are the sorts of things that would not
ordinarily be deduced.
This is a first order solution to the problem of giving the system
an indication of its weaknesses. A better solution would supply an
indication of how much it knows about a subject, as compared with how much
there is to know. There surely are subjects for which three or four rules
exhaust the available knowledge, while for others a hundred or more rules
may not suffice. The issue is related to work described in [Carbonell73],
on closed vs. open sets. That paper offers some interesting strategies for
allowing a program to decide when it is ignorant and how it might reason
in the face of the inability to store every fact about a given topic.
There appear to be no easy ways to deduce the incompleteness of the
knowledge base using only the information stored in it. It is not valid to
say, for instance, that there ought to be even a single rule for every
attribute (how could a patient's name be deduced?). Nor is there a
well-defined set of attributes for which no rules are likely to exist. Nor is
it clear what sort of information would allow the incompleteness to be
deduced.
The issue is a significant one, since a good solution to the problem would not
only give {\TEIRESIAS} a better grasp of where the performance program was weak but would also
provide several important capabilities to the performance program itself. It would,
for example, permit the use of the ``if it were true I would know'' heuristic in
[Carbonell73]. Roughly restated, this says that ``if I know a great deal about
subject S, and fact F concerns an important aspect of S, then if I don't already know
that F is true, it's probably false.'' Thus, in certain circumstances a lack of
knowledge about the truth of a statement can plausibly be used as evidence suggesting
that the statement is false.\ffnote{Note that this is another, very useful, form of
meta-level knowledge.}
\sectionskip
\sectionbegin[6]{Personalized world views}
One of the likely problems of collecting knowledge from several
experts is that of conflicting world views. Since, currently, individual
modifications to the rule base are stored away separately for each
individual user, the established knowledge base is kept distinct from local
modifications. At some time, however, it might prove useful to be able to
deal with contributions from several experts and keep them in the
knowledge base all at once. Some very limited capabilities in this
direction are made possible by tagging each rule with the name of its
author (as illustrated earlier) and by building a set of rule models for
each individual's personal knowledge base.
Individualized rule models make it possible, for instance, to ask
the system {\sl How would Dr. Jones deduce the identity of an organism?} and to
compare this with the reasoning indicated by a rule model for a different
expert. The tags on rules make it possible to focus conveniently on the
effects of the contributions of different experts. We can imagine, for
instance, a meta-rule of the form {\sl When trying to deduce the identity of an
organism, only use rules written by Dr. Jones or Dr. Smith}, or {\sl \ellipsis only
those written by the expert currently running the program}. (There might
even be a preference ordering on the rules, based on length of experience of
the rule author. See chapter 7 for the details of meta-rule operation.)
Using both of these capabilities, it is possible to see both how a given
expert reasons about a subject and how he might handle a single, given
aspect of a case.
While this provides a handle on manipulating different world views,
it clearly does not confront the deeper problem of resolving any conflicts
between them. More work on this subject is required.
\sectionskip
\sectionbegin[7]{More on models and concept formation}
Now that the organization, structure,
and function of rule models in the system\!
\comment{.beginind models .beginind model-based understanding}\index{ concept formation}
\ is clear, let's take another look at the general idea of models, concept formation,
and model-based understanding.
\subsectionbegin[7.1]{Model-Based Understanding}
Many AI programs have incorporated explicit models and used them as
a guide to understanding. The work of Falk and Roberts in vision has been
mentioned; the idea has been extended to a range of other sensory
modalities as well. Viewed in the broadest terms, the process may be
considered one of signal interpretation, as suggested by the figure below.
% .STARTFIG;
% .BOXFIG;
% ⊂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂⊃
% ←∂∂∂∂interpretation∂∂∂ } signal processor } ←∂∂∂∂signal∂∂∂
% α%∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
% ↑
% ⊂∂∂∂∂∂∂∂∂∂⊃ }
% } model } ∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂$
% α%∂∂∂∂∂∂∂∂∂$
% .FIG (Simple view of model-based understanding,);
% .ENDFIG;
\vskip 7pc
\figtitle 5-9{Simple view of model-based understanding.}
\noindent
Some signal-processing operation is performed on the incoming signal, with
guidance and/or advice from a model. The result is an interpretation of
the signal (or some action based on it), which gives evidence that it was
understood. The table below lists six different systems that can be
viewed in these terms (including ours) and compares them along several
dimensions.
% .STARTFIG;
% .TABLE(Model-based systems,MBSTABLE:);
% .BOXFIG;
%
% ∂∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂∂∂π∂∂∂∂∂∂∂π∂∂∂∂∂∂∂∂∂∂∂∂∂∂
% Reference }Signal } Model }Model } Evidence of
% } } }type } understanding
% ∂∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂β∂∂∂∂∂∂∂β∂∂∂∂∂∂∂∂∂∂∂∂∂∂
% [Falk70] }Light }Polyhedra }Object }Synthesized
% } } } }reconstruction
% } } } }of picture
% } } } }
% [Winograd72] }English }Blocks world }World }Block
% }text } } }manipulation,
% } } } }coherent
% } } } }dialogue
% } } } }
% [Waltz72] }Line }Vertex }World }Analysis of
% }drawings }classification} }picture
% } } } }
% [Reddy73] }Sound }Chess game }World }Typed version
% } } } }of spoken
% } } } }sentence
% } } } }
% [Goldstein74]}Annotated }Verbal }World }Debugged
% }program }description of} }program
% } }picture } }
% } } } }
% Davis }English }Rule models, }Object }Retranslated
% } }medical }world }rule
% } }knowledge base} }
% ∂∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∀∂∂∂∂∂∂∂∂∂∂∂∂∂∂
%
% .ENDFIG;
\topinsert{\vskip 20pc\tablenum 5-1{Model-based systems.}}
The examples illustrate the two sorts of models in use.
``World model'' is used in the usual sense and refers to a collection of
information that characterizes the domain of interest. The system described in
[Reddy73], for example, had a model of the world of chess that included
information about plausible moves and appropriate vocabulary. The vision system
in [Waltz72] contained a complete classification of the types of vertices that
could be a part of a convex planar-faced polyhedron and used this as its model
of the blocks world.
An ``object model,'' on the other hand, is used to characterize the expected
content of the signal to be processed. Falk's system, for example, had models
of the individual polyhedra from which scenes would be constructed.
Understanding a scene was then viewed in terms of choosing specific models and
assigning locations and orientations to each.
The two sorts of models tend to be used somewhat differently.
In very general terms, we can say that since object models provide
characterizations of signal content, ``understanding'' can be approached as a
comparison between the model and the signal. World models provide a source of
knowledge that is typically used to check the plausibility of potential
interpretations of the signal. Object models are thus typically used in some
manner of matching process, while world models are used inferentially.
The two models are really at either extreme of the continuum shown
below, which emphasizes the distinction by considering two vision programs
that performed similar tasks.\ffnote{Remember that selected aspects of each
program have been singled out here for the sake of discussion. All of the
programs here and in Table 5--1 were more complex than the simple
characterizations given.} Where Falk's program had models of individual
polyhedra (models characterizing the signal content), Waltz's program used
knowledge about the ``world'' of polyhedra in general, without reference to
any specific instance.
\null\nofill%
MODEL PROCESS EXAMPLE
World model Inferential [Waltz72]
Object model Matching [Falk70]
\endnofill
\figtitle 5-{10}{Object models and world models: Comparison.}
The rule models used in {\TEIRESIAS} fall somewhere in between. They are
a type of object model, since they represent the content expected in the signal.
But they are not themselves rules and cannot therefore simply be matched
against the signal. The information they carry, however, can be used to help
direct the interpretation process. In
addition, the knowledge base provides the system with a world model.
As will become clear in the next chapter, the knowledge base contains many data
structures that indicate such things as which values belong with which attributes.
The system relies on this information to maintain the internal consistency of
the clauses it assembles and will, as a result, never produce a clause of the
form ``{\tt The site of the culture is e.coli.}''
\subsectionbegin[7.2]{Concept Formation}
There has also been much work done in AI on concept formation; a
recent example noted earlier is [Winston70]. A much simplified view of
the information flow in the task is shown below, where a set of examples is
used as the basis for inferring a concept.
% .STARTFIG;
% .BOXFIG;
% ⊂∂∂∂∂∂∂∂∂∂∂⊃
% } examples }
% α%∂∂∂∂∂∂∂∂∂∂$
% } ⊂∂∂∂∂∂∂∂∂∂∂⊃
% α%∂∂∂∂∂∂∂∂∂∂∂→ } concept }
% concept α%∂∂∂∂∂∂∂∂∂∂$
% formation
% .FIG (Simplified view of concept formation,);
% .ENDFIG;
\vskip 7pc
\figtitle 5-{11}{Simplified view of concept formation.}
\subsectionbegin[7.3]{A Synthesis}
Now consider the process of model-directed understanding combined with
concept formation, producing the figure below. In terms of our system, the
``signal'' is the new rule text, ``signal processing'' is done by the
rule acquisition routines, the interpretation is the new rule in {\sc LISP}
terms, and the ``model'' is provided by the set of rule models. For concept
formation, the rule base supplies the examples from which the concepts---the
rule models---are constructed.
% .STARTFIG;
% .BOXFIG;
%
% ⊂∂∂∂∂∂∂∂∂∂∂∂⊃ [knowledge ⊂∂∂∂∂∂∂∂∂∂∂∂⊃
% } KNOWLEDGE } ← ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ } RULE } ← ∂ ∂ ∂ ∂ EXPERT
% } BASE } acquisition] }ACQUISITION} [dialog]
% α%∂∂∂∂∂∂∂∂∂∂∂$ α%∂∂∂∂∂∂∂∂∂∂∂$
% } ↑
%
% } }
%
% } ⊂∂∂∂∂∂∂∂∂∂∂⊃ }
% } RULE } [model-directed
% α% ∂ ∂ ∂ ∂ →} MODELS } ∂ ∂ ∂ ∂ $ understanding]
% [concept α%∂∂∂∂∂∂∂∂∂∂$
% formation]
% .WIDECAPFIG(Synthesis of concept formation and model-based understanding);
% .ENDFIG;
\vskip 9pc\figtitle 5-{12}{Synthesis of concept formation and model-based
understanding.}
The result is an interesting form of closed-loop behavior. The
existing rule models are used to guide the process of acquisition, the new
rule is added to the knowledge base and the relevant rule models are
recomputed. The system is thus constructing its models (its picture of its
own knowledge) on the basis of experience, keeping those models up-to-date
with the current knowledge base and using them to help acquire new
knowledge.
This loop has a number of interesting implications. First,
performance on the acquisition of the next rule may be better because the
system's ``picture'' of its knowledge base has improved---the rule models are
now computed from a larger set of instances and their generalizations are
more likely to be valid.
Second, since the relevant rule models are recomputed each time a
change is made to the knowledge base, the picture they supply is kept
constantly up-to-date; thus, they are at all times an accurate reflection
of the shifting patterns in the knowledge base.
Finally, and perhaps most interesting, the models are not
hand-tooled by the system architect or specified by the expert. They are
instead formed by the system itself and formed as a result of its
experience in acquiring rules from the expert. Thus, despite its reliance
on a set of models as a basis for understanding, {\TEIRESIAS}'s abilities are not
restricted by the existing set of models. As its store of knowledge grows,
old models become more accurate, new models are formed, and the
system's stock of knowledge about its knowledge continues to expand.
This appears to be a novel capability for a model-based system.
\comment{.endind models .endind model-based understanding}
\sectionskip
\sectionbegin[8]{Assumptions and Limitations}
As noted, our approach involves knowledge transfer that is interactive,
that is set in the context of a shortcoming in the knowledge base, and that
transfers a single rule at a time. Each of these has implications about {\TEIRESIAS}'s
range of applicability.
Interactive knowledge transfer seems best suited to task domains involving
problem solving that is entirely or primarily a high level cognitive task, with
a number of distinct, specifiable principles. Consultations in medicine or
investments seem to be appropriate domains, but the approach would not seem
well suited to those parts of, say, speech understanding or scene recognition
in which low level processes play a significant role.
The transfer of expertise approach presents a useful technique for task
domains that do not permit the use of programs (like those noted in chapter 4) which
autonomously induce new knowledge from test data. This may occur most commonly
because the data for a domain simply don't exist yet. In quantitative domains (like
mass spectrum analysis [Mitchell78]) or synthesized (``toy'') domains (like the line drawings
in [Waltz75]), a large body of data points is easily assembled. This is not currently
true for many domains, consequently induction techniques cannot be used. In such cases
interactive transfer of expertise offers a useful alternative.
Knowledge acquisition in context appears to offer useful guidance
wherever knowledge of the domain is as yet ill-specified, but the context need
not be a shortcoming in the knowledge base uncovered during a consultation, as
is done here. Our recent experience suggests that an effective context is also
provided by examining certain subsets of rules in the knowledge base and using
them as a framework for specifying additional rules. The overall concept is limited,
however, to systems that already have at least some minimal amount of
information in their knowledge base. Earlier than this, there may be
insufficient information to provide any context for the acquisition process.
Finally, the rule-at-a-time approach is a limiting factor. The example
given earlier works well, of course, because the bug was manufactured by
removing a single rule. In general, acquiring a single rule at a time seems
well suited to the later stages of knowledge base construction, in which bugs
may indeed be caused by the absence of one or a few rules. We need not be as
lucky as the present example, in which one rule repairs three bugs; the approach
will also work if three independent bugs arise in a consultation. But early in
knowledge base construction, where large sub-areas of a domain are not yet
specified, it appears more useful to deal with groups of rules, or, more
generally, with larger segments of the basic task (as in [Waterman78]).
In general then, the interative transfer of expertise approach seems
well suited to the later stages of knowledge base construction for systems
performing high-level tasks, and offers a useful technique for domains where
extensive sets of data points are not available.
\sectionskip
\sectionbegin[9]{Unsolved problems and future work}
There are a number of problems left unsolved by the current
implementation that suggest several directions for future work. They are
of two forms: minor problems whose solution involves extensions and
refinements to existing methods, and major problems requiring new
solutions.
\subsectionbegin[9.1]{Minor Problems}
As with all first-generation systems, {\TEIRESIAS} has many rough spots and
inconveniences. These will have to be smoothed out before the acquisition
routines can become a powerful user-oriented system. For instance, the
system's guidance of the debugging process could be improved. It currently
derives
much power from its methodical approach, forcing the expert's
criticism to be sharply focused. But it is also somewhat inflexible and
unforgiving: In most cases there is no way to change a response once a
question is answered, for instance.
There are other tasks suggested by the larger context in which
acquisition occurs. It would be useful, for example, to provide several
sorts of feedback on the consultation system's performance. A recent
addition to {\sc MYCIN} keeps extensive statistics on the use of each
rule in the knowledge base. These should be routinely scanned by the
acquisition system to detect potential bugs (\eg, a rule that is never
invoked successfully is likely to have an error in its premise). A more
sophisticated solution might even be capable of suggesting plausible
corrections, based on an examination of the situations under which failure
occurred. It should also be possible to provide some feedback after the
complete information on a case is available. Original diagnoses, for
instance, could be evaluated in light of the final results from the
laboratory, possibly suggesting modifications to the knowledge base.
The rule editor could also be improved in several respects. It
should be possible, for instance, to make a number of routine changes to a
rule with less machinery than is currently used. The rule editor can
currently be invoked separately to accomplish some of these, but
it would require a
larger command set to be adequately powerful. A more substantive
improvement concerns the problem noted earlier, of knowing exactly what to
change and what to delete in a rule that has been misunderstood. While the
primitive approach to natural language is the fundamental source of the
problem (see below), there are several things that could be done to ease
the difficulties. It would be a great help simply to make clear which
interpretations came from which lines of the original input text. This
might be done as easily as grouping the appropriate lines together as they are
printed, making the nature of the system's misunderstandings more obvious.
Since the process of tracking down the original problem in the
knowledge base is easily viewed as diagnosis and therapy, there is the
interesting possibility of expressing it
too in rules. Such a body of rules would allow
running a ``mini-consultation'' to uncover the problem and initiate
corrective action. It would have the substantive advantage of allowing all
the explanation (and conceivably, acquisition) routines to be used during
the debugging process. Rules to do this have been drafted but have not
yet been implemented.
\subsectionbegin[9.2]{Major Problems}
\subsectionbegin[9.2.1]{Better Techniques for Rule Model Generation}
The shortcomings of the present approach to rule model generation
were outlined earlier. The primary
problem is the use of a purely statistical approach to concept formation.
This approach was motivated, in part, by the desire to make the models
transparent to the expert. More sophisticated sorts of concept
formation would be possible if the model construction process were made
interactive. With this approach, each time a change had been made to the
knowledge base, {\TEIRESIAS} would indicate to the expert any new patterns that had
become evident and would ask him for an evaluation of each. With this sort of
advice, it would become possible to distinguish accidental correlations
from valid interrelations. It would also be possible to construct
models with a much finer degree of\index{ second guessing}
control. The utility and sophistication of {\TEIRESIAS}'s second guessing would
increase proportionally.
\subsectionbegin[9.2.2]{Natural Language}
Of the major problems, the weakness of the natural language understanding
techniques presents the largest barrier to better performance.
Even without introducing more sophisticated grammar-oriented techniques,
however, there are several steps that might be taken to strengthen the
system. Processing each line of the text independently is one source of
weakness. The rule models are currently used to score the interpretation
of each line independently, but the ntuples might easily be used to score
an entire premise at once.
\index{ consistency}Also, as shown, there is substantive advantage in being careful
about the consistency of the parses generated for a single line of text. A
similar technique should be developed to consider consistency between
lines. This is a much harder problem, however, since it requires a
considerably large store of world knowledge. For instance, it makes sense
to have a rule say {\sl if the identity of an organism is likely to be X and
likely to be Y} (\ie, there's evidence for both X and Y). But it does
not make sense to say {\sl if the site of the culture is likely to be X and
likely to be Y}, because the site from which a culture is obtained is
rarely in doubt. This requires more knowledge about things like identities
and sites than currently exists in the system, or than is easily added.
Another manifestation of the weakness of the line-by-line treatment
of natural language appears in the way the English versions of the rules
are printed. Some rules are quite awkward when translated line by line,
yet often they have very simple restatements in other terms. More sophisticated
translation routines should be developed to handle an entire rule at once.
There are obvious weaknesses, too, in the word-by-word approach to
meaning. As the knowledge base grows larger, significant numbers of
attributes are beginning to use similar terms. The appearance of that term
in text then yields numerous connotations and an awkwardly large number of
clauses are generated.
The rule models should also be integrated deeper into the
natural language interpretation process. Rather than generating all the parses,
the models should be used to help choose which branch of the parse tree to
explore. The tree would be generated a path at a time, under the guidance
of the rule model, which might be far more efficient and have a better
chance of arriving at the right answer sooner.
\subsectionbegin[9.2.3]{Impact on the Knowledge Base}
There is a rather vast problem, which we have examined only very
briefly, concerning the impact of any new or changed rule on the rest of
the knowledge base.\ffnote{See [Shortliffe76] for additional thoughts on this
topic.} There are two general classes of interactions, corresponding to
syntactic and semantic conflicts. The difficulty in syntactic problems
arises out of the use of certainty factors. Except in very simple cases
(\eg, two rules identical except for their CFs), there is some question of
what constitutes contradiction and subsumption for this form of
reasoning\index{ contradiction}\index{ subsumption} rule.
\index{ consistency}The lack of a precise definition of inconsistency makes detecting
indirect contradictions (which result from chaining several rules together)
especially diffi\-cult. As an example, consider the rules below. They are
valid under the current CF model but would be a contradiction in ordinary
binary-valued logic. (A well-specified set of organisms belong to a given
category, so just knowing the category of an organism gives a hint about
its identity. But the rule set below is plausibly correct if all the
members of the category except one [identity A] have the same aerobicity.)
% .STARTFIG;TABS 16;TURN ON ''\'';
% R1: \CATEGORY is X %5===%* .4 %5===@%* IDENTITY is A
% .ONCE SELECT 1;FILL; ADJUST; SPACING 20 MILLS; PREFACE 20 MILLS;INDENT 15,15,15;
% [Knowing category is X gives some hint of identity.]
% .apart
% .skip;
% .group
% R2: \IDENTITY is A %5===%* -1 %5===@%* AEROBICITY is B
% .ONCE SELECT 1;FILL; ADJUST; SPACING 20 MILLS; PREFACE 20 MILLS;INDENT 15,15,15;
% [Knowing identity is A can be used definitely to rule out the aerobicity
% value which is different than the aerobicity of A.]
% .apart
% .skip;
% .group
% R3: \CATEGORY is X %5===%* .2 %5===@%* AEROBICITY is B
% .ONCE SELECT 1;FILL; ADJUST; SPACING 20 MILLS; PREFACE 20 MILLS;INDENT 15,15,15;
% [But the category is evidence about aerobicity also,
% and might indicate that it's B, if all the other members of the category
% have aerobicity B.]
% .ENDFIG;
% .continue
\topinsert{\vskip 14pc \figtitle 5-{13}{}}
Thus, there are two patterns of the form
\centerit{\tt CATEGORY $=$ .4 $\→$ IDENTITY $=$ $-$1.0 $\→$ AEROBICITY}
and \centerit{\tt CATEGORY $=$ .2 $\→$ AEROBICITY}
In this way, {\tt CATEGORY} can be both evidence in favor of and against
{\tt AEROBICITY}, depending on the reasoning chain used.\ffnote{This is not
unreasonable. Conditional probabilities in standard Boolean logic present
an analogous situation. Given an hypothesis H and a piece of evidence E, E
can be both evidence in favor of H (P[H|E] = .8) and evidence in favor of
not-H (P[not-H|E] = .2).} Now consider what happens if the CFs for R1 and
R3 above are changed slowly and allowed to approach 1.0. Since the CF
model becomes Boolean logic when all CFs are either 1.0 or $-$1.0, at some
point the rule set above will become inconsistent; but the question is
when.
Boolean logic has the constraint that P(H|E) + P(not-H|E) = 1.0, an
equality from which the value of either probability can be computed when
given the other. For CFs there may conceivably be an inequality from which
to compute the legal range of a certainty factor for one rule in a
particular set of rules, but it has not been derived as yet. The first
step in detecting inconsistencies is thus to define the concept more
precisely.
Even with a rigorous definition, however, the problem of
inconsistency detection would remain difficult. One possible approach
would be to view the rule base as a directed graph, where nodes correspond
to attributes, and links correspond to rules, with weights on the links
equal to the certainty factors of the rules. In these terms, the example
above would look like two different paths from category to aerobicity. We
might then attempt to develop a taxonomy of topologic forms that were
``suspicious'' and take the proper action (or just warn the expert) if a new
rule ever resulted in such a form. (Note that the problem is a good deal
easier with this incremental approach. By guaranteeing the integrity of
the current knowledge base, there is far less work to do when a new rule is
added.)
``Semantic'' conflicts are more difficult to handle. How, for
instance, can the system know that it is a contradiction to have two rules
conclude that {\sl it is definite that the
site of the culture is one of the sterile sites} and that {\sl it is definite
that the site is one of the nonsterile sites}. The important point is
that these two classes are mutually exclusive. There might be a rule of
the form {\sl if a site is sterile then it is not nonsterile}, but attempting
to account for such problems on a case-by-case basis is difficult to do for
any large knowledge base. Consider, for instance, the difficulty that would
be encountered when it became clear that the two classes are not
exhaustive and that there is a third class of sites that are
``questionably'' sterile. A more fundamental solution to the problem
requires, once again, an extensive body of world knowledge not currently a
part of the system. We have not yet investigated the question of dealing
with this sort of conflict.
\subsectionbegin[9.2.4]{Limits of the Interactive Transfer of Expertise Approach}
While {\TEIRESIAS} has not as yet been tested by having experts use it, our
experience with manual knowledge acquisition provides a perspective on its
likely area of greatest utility. As noted, our approach involves
knowledge\index{ knowledge acquisition in context}
transfer that is interactive, that is set in the context of a shortcoming
in the knowledge base, and that transfers a few rules at a time. Each of
these implies certain constraints on the range of applicability of this
system.
Interactive knowledge transfer seems best suited to task domains
involving problem solving that is entirely or primarily a high-level
cognitive task, with a number of distinct, specifiable principles. Medical
diagnosis seems an appropriate domain, but the technique would not seem
well suited to those parts of, say, speech understanding or scene
recognition in which low-level processes appear to play a significant role.
Knowledge acquisition in context appears to offer a useful guide
wherever knowledge of the domain is as yet ill-specified, but the context
need not be a single consultation, as used here. Our recent experience
suggests that an effective context is also provided by examining certain
subsets of rules in the knowledge base, using them as a framework for
specifying new rules.
Finally, the rule-at-a-time approach is perhaps the most limiting
factor. The example given earlier works well, of course, because the bug
was manufactured by removing a single rule. In general, the approach seems
well suited to the later stages of knowledge base construction, in which
bugs may indeed be caused by the absence of one or a few rules. We need
not be as lucky as the present example, in which one rule repairs three
bugs; the approach will also work if three independent bugs arise in a
given consultation. But early in knowledge base construction, where large
sub-areas of a domain are not yet specified, it appears more useful to deal
with groups of rules or, more generally, to deal with larger segments of the
basic task, as for example in [Waterman77].
In general, then, this approach seems well suited to the later
stages of knowledge base construction for systems performing high-level
tasks.
\sectionskip
\sectionbegin[10]{Summary}
This chapter has explored and illustrated a number of issues.
First, by doing knowledge acquisition in the context of a shortcoming in
the knowledge base, {\TEIRESIAS}'s acquisition system can build up a set of
expectations about the class of rule it is going to get.
Second, in the set of rule models {\TEIRESIAS} has a model of the
information in the knowledge base, and it is by selecting one part of that
model (a specific rule model) that it expresses its expectations.
Third, because it has a model of the knowledge base, {\TEIRESIAS} can tell
whether some new piece of information ``fits in'' to what is already known.
It is the occurrence of a partial match between the expectations in the
rule model and the new rule that prompts the system to make suggestions to
the expert.
Fourth, the rule models are computed directly from the set of rules
in the knowledge base and are updated whenever a new rule is added. This
means that the system's model of its knowledge is both derived from its
``experience'' and constantly evolving along with the knowledge base itself.
\worldend